§1C, proof of Proposition 2, p. 41 — every eigenvalue β of P satisfies β ≥ −1 + 2/ι
ProvedDiaconisStroock.OddPaths.eigenvalue_geeigenvaluemarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1path-system
Let be an irreducible transition matrix on a finite set , reversible with respect to its stationary distribution , let be a system of odd closed paths and the quantity (1.7). Then every real eigenvalue of (a real with for some nonzero real ) satisfies
This is the sentence that closes the proof of Proposition 2: dividing the inequality by for an eigenfunction gives a lower bound on any eigenvalue of .
Formalization Note Aperiodicity is not assumed, as in the previous milestone. Eigenvalues are real eigenvalues with real eigenfunctions; for a reversible chain all eigenvalues are of this kind.
Preamble
import Mathlib import Definitions.Def_mm_spectral import Definitions.Def_DiaconisStroock_OddPaths_Iota open MarkovMixing
Formal statement
namespace DiaconisStroock.OddPaths
theorem eigenvalue_ge {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) :
∀ β : ℝ, IsEigenvalue P β → -1 + 2 / iota P π S ≤ β := by sorry
end DiaconisStroock.OddPaths
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), p. 41, §1C, end of the proof of Proposition 2, https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.