Proposition 2, p. 40 — β_min ≥ −1 + 2/ι for an irreducible aperiodic reversible chain and any system Σ of odd closed paths
ProvedDiaconisStroock.OddPaths.proposition_2Let be a finite set and the transition matrix of an irreducible, aperiodic Markov chain on , reversible with respect to its stationary distribution : . Let be the smallest eigenvalue of .
For each let be a path from to with an odd number of edges, along edges with (self-loops included) and with no directed edge traversed twice, and let . With and
(the maximum over directed edges), for every such :
The aperiodic chain is exactly the case ; this proposition makes that quantitative, and together with Proposition 1 it bounds the absolute spectral gap , , which governs convergence to stationarity.
Formalization Note is the infimum of the real eigenvalues of . The paper defines "by analogy with (1.4)", whose paths may not repeat an edge; for §1C's directed edges the rule is read as "no directed edge is traversed twice", which keeps the page's claim that such paths exist for every irreducible aperiodic chain. The system is universally quantified, as in "for any choice". No assumption is made: on a one-point space the bound reads .
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_OddPaths_Iota open MarkovMixing
namespace DiaconisStroock.OddPaths
theorem proposition_2 {V : Type*} [Fintype V] [DecidableEq V] (P : Matrix V V ℝ)
(hP : IsStochastic P) (hirr : MarkovMixing.Irreducible P) (haper : Aperiodic P) (π : V → ℝ)
(hπ : IsStationary P π) (hrev : DetailedBalance P π) (S : V → List V)
(hS : IsOddPathSystem P π S) :
-1 + 2 / iota P π S ≤ betaMin P := by sorry
end DiaconisStroock.OddPaths
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.