§1C, proof of Proposition 2, pp. 40–41 — E(φ²) ≤ (ι/2)(E(φ²) + ⟨φ, Pφ⟩_π)
ProvedDiaconisStroock.OddPaths.inner_self_le_iota_muleigenvaluemarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1path-systempoincare-inequality
Let be an irreducible transition matrix on a finite set , reversible with respect to its stationary distribution , and . Let be a system of odd closed paths (each runs from to along edges with , has an odd number of edges and traverses no directed edge twice), and let be the quantity (1.7). Then for every ,
where and .
This is the Poincaré-type inequality for the operator that yields Proposition 2: applied to an eigenfunction it bounds the eigenvalue from below.
Formalization Note Aperiodicity, a hypothesis of Proposition 2, is not assumed: once a system of odd paths is given, the inequality holds without it (and the existence of such a system forces it).
Preamble
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_OddPaths_Iota open MarkovMixing
Formal statement
namespace DiaconisStroock.OddPaths
theorem inner_self_le_iota_mul {V : Type*} [Fintype V] [DecidableEq V] (P : Matrix V V ℝ)
(hP : IsStochastic P) (hirr : MarkovMixing.Irreducible P) (π : V → ℝ) (hπ : IsStationary P π)
(hrev : DetailedBalance P π) (S : V → List V) (hS : IsOddPathSystem P π S) :
∀ φ : V → ℝ,
innerPi π φ φ ≤ iota P π S / 2 * (innerPi π φ φ + innerPi π φ (P.mulVec φ)) := by sorry
end DiaconisStroock.OddPaths
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), pp. 40–41, §1C, proof of Proposition 2 (the displayed chain of inequalities), https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.