Proposition 1 — β₁ ≤ 1 − 1/κ for reversible chains
ProvedDiaconisStroock.Poincare.proposition_1eigenvaluemarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1poincare-inequalityspectral-gap
Let be an irreducible transition matrix on a finite state space with at least two states, reversible with respect to its stationary probability distribution . For every choice of one edge-simple path for each ordered pair , let be the directed-edge congestion in (1.5). If is the second largest eigenvalue of , then
This is the paper's first geometric bound on a Markov chain eigenvalue: a path system with low congestion yields a quantitative spectral gap.
Formalization Note The hypothesis makes exist. The path system is universally quantified, as the paper says “for any choice of .”
Preamble
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_Poincare_Kappa
Formal statement
namespace DiaconisStroock.Poincare
open MarkovMixing
/-- Proposition 1 (Poincaré inequality), p. 37, with κ defined by (1.5). -/
theorem proposition_1 {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : MarkovMixing.Irreducible P)
(π : V → ℝ) (hπ : IsStationary P π) (hrev : DetailedBalance P π)
(hV : 2 ≤ Fintype.card V) (Γ : V → V → List V) (hΓ : IsPathSystem P π Γ) :
lambdaTwo P ≤ 1 - 1 / kappa P π Γ := by sorry
end DiaconisStroock.Poincare
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), p. 37, Proposition 1 and (1.5), https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.