§1D, proof of Proposition 3, p. 42 — diagonal bound P^{2n}(x,x) ≤ π(x) + β_*^{2n}(1 − π(x))
ProvedDiaconisStroock.VarDist.pow_two_mul_diag_leLet be a finite set with elements and the transition matrix of an irreducible Markov chain on , reversible with respect to its stationary probability distribution . Its eigenvalues are real, , and
is the largest modulus of an eigenvalue other than . Then for every state and every ,
In the paper this comes from the spectral expansion , where the eigenvalue contributes and the remaining weights sum to . Combined with the Cauchy–Schwarz bound it gives (1.9).
Formalization Note is MarkovMixing.lambdaStar P, the supremum of over real eigenvalues of . For an irreducible reversible chain the eigenvalue is simple and all eigenvalues are real, so this set is and its maximum is . When the set is empty and lambdaStar P = 0; the inequality then reads , still true, so no hypothesis is needed. is included (both sides equal ).
import Mathlib import Definitions.Def_mm_spectral open MarkovMixing
namespace DiaconisStroock.VarDist
/-- The diagonal bound in the proof of Proposition 3 (Diaconis and Stroock, Geometric bounds for
eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), §1D, proof of Proposition 3, p. 42):
for an irreducible chain `P` reversible with respect to its stationary distribution `π`,
`P^{2n}(x, x) ≤ π(x) + β_*^{2n} (1 − π(x))`, where `β_* = lambdaStar P` is the largest modulus of
an eigenvalue different from `1`. -/
theorem pow_two_mul_diag_le {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : MarkovMixing.Irreducible P)
(π : V → ℝ) (hπ : IsStationary P π) (hrev : DetailedBalance P π) :
∀ (x : V) (n : ℕ), (P ^ (2 * n)) x x ≤ π x + lambdaStar P ^ (2 * n) * (1 - π x) := by sorry
end DiaconisStroock.VarDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.