Proposition 3, (1.9), pp. 41–42 — 4‖Pⁿ(x,·) − π‖²_Var ≤ ((1 − π(x))/π(x)) β_*^{2n} for reversible chains
ProvedDiaconisStroock.VarDist.proposition_3Let be a finite set with elements and the transition matrix of an irreducible Markov chain on , reversible with respect to its stationary probability distribution :
The eigenvalues of are real, ; put . The variation distance between probability distributions on is .
Proposition 3, (1.9). For every starting state and every ,
This is the basic eigenvalue bound on the distance to stationarity of a reversible chain: once is bounded away from (for instance by the geometric bounds of Propositions 1 and 2 of the same paper), it gives an explicit number of steps after which the chain started at is close to in variation distance.
Formalization Note The chain is a real matrix P with IsStochastic P, MarkovMixing.Irreducible P, a stationary probability vector π (IsStationary P π) and detailed balance DetailedBalance P π. is tvDist (rowDist P n x) π, and is lambdaStar P, the supremum of over real eigenvalues of , which equals for an irreducible reversible chain (the eigenvalue is simple and all eigenvalues are real). Positivity of is not assumed: it follows from irreducibility and stationarity. The case is included; there the bound reads , which holds because . On a one-point space both sides are (the eigenvalue set is empty and lambdaStar P = 0), so no hypothesis is added.
import Mathlib import Definitions.Def_mm_spectral open MarkovMixing
namespace DiaconisStroock.VarDist
/-- **Proposition 3, (1.9)** (Diaconis and Stroock, Geometric bounds for eigenvalues of Markov
chains, Ann. Appl. Probab. 1 (1991), pp. 41–42): for an irreducible chain `P` on a finite set,
reversible with respect to its stationary distribution `π`,
`4‖Pⁿ(x, ·) − π‖²_Var ≤ ((1 − π(x))/π(x)) β_*^{2n}` for every state `x` and every `n`, where
`β_* = lambdaStar P = max(β₁, |β_{m−1}|)`. -/
theorem proposition_3 {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 : ℕ),
4 * tvDist (rowDist P n x) π ^ 2 ≤ (1 - π x) / π x * lambdaStar P ^ (2 * n) := by sorry
end DiaconisStroock.VarDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.