Proposition 7: β₁ ≤ 1 − 1/(8η²)
ProvedDiaconisStroock.CanonPaths.proposition_7canonical-pathscheeger-inequalityeigenvaluemarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a reversible irreducible Markov chain on a finite set of at least two states, with stationary distribution . Choose a positive-flow walk for every distinct ordered pair and define its directed-edge congestion by (3.2). If is the second largest eigenvalue of , then
The bound estimates the second eigenvalue using a geometric load imposed by the chosen walks. It is the central result of this mission.
Formalization Note The at-least-two-states condition makes well defined. The Lean walk system only constrains distinct endpoints; equal-endpoint choices are ignored by . The theorem assumes neither the intermediate bottleneck bound nor Cheeger's inequality.
Preamble
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_CanonPaths_Eta
Formal statement
namespace DiaconisStroock.CanonPaths
open MarkovMixing
/-- Proposition 7, p. 54: the second eigenvalue is bounded by the congestion of any
system of canonical walks on an irreducible reversible chain. -/
theorem proposition_7 {V : Type*} [Fintype V] [DecidableEq V]
(hV : 2 ≤ Fintype.card V) (P : Matrix V V ℝ) (hP : IsStochastic P)
(hirr : MarkovMixing.Irreducible P) (π : V → ℝ) (hπ : IsStationary P π)
(hrev : DetailedBalance P π) (Γ : V → V → List V)
(hΓ : IsWalkSystem P π Γ) :
lambdaTwo P ≤ 1 - 1 / (8 * eta P π Γ ^ 2) := by sorry
end DiaconisStroock.CanonPaths
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), p. 54, Proposition 7 and (3.2); https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.