§1B, proof of Proposition 1 — variance bounded by κ times Dirichlet energy
ProvedDiaconisStroock.Poincare.var_le_kappa_mul_dirichletmarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1poincare-inequalityspectral-gapvariance
Let be an irreducible stochastic transition matrix on a finite state space, reversible with respect to a stationary probability distribution . Choose an edge-simple path for each ordered pair of distinct states, and let be the directed-edge congestion in (1.5). Then every real function satisfies
where . This functional inequality is the step immediately before the spectral conclusion of Proposition 1.
Formalization Note The valid path system excludes repeated unordered edges. The statement also covers a one-state chain, for which both sides are zero.
Preamble
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_Poincare_Kappa
Formal statement
namespace DiaconisStroock.Poincare
open MarkovMixing
/-- The Poincaré inequality reached in the proof of Proposition 1, p. 38. -/
theorem var_le_kappa_mul_dirichlet {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : MarkovMixing.Irreducible P)
(π : V → ℝ) (hπ : IsStationary P π) (hrev : DetailedBalance P π)
(Γ : V → V → List V) (hΓ : IsPathSystem P π Γ) (φ : V → ℝ) :
distVar π φ ≤ kappa P π Γ * dirichletForm P π φ := by sorry
end DiaconisStroock.Poincare
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), p. 38, §1B, proof of Proposition 1, final display, https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.