§1D, proof of Proposition 3, p. 42 — Cauchy–Schwarz bound 4‖Pⁿ(x,·) − π‖²_Var ≤ P^{2n}(x,x)/π(x) − 1
ProvedDiaconisStroock.VarDist.four_tvDist_sq_leLet be a finite set and the transition matrix of an irreducible Markov chain on , reversible with respect to its stationary probability distribution . For probability distributions on the variation distance is
Then for every starting state and every , the distribution of the chain after steps satisfies
This is the first half of the proof of Proposition 3: it bounds the variation distance by an quantity (a distance) and then by a diagonal entry of .
Formalization Note is MarkovMixing.tvDist μ π, defined as the supremum over subsets of , and is rowDist P n x. The square binds before the factor . Positivity of is not assumed; it follows from irreducibility and stationarity. is included.
import Mathlib import Definitions.Def_mm_mixing open MarkovMixing
namespace DiaconisStroock.VarDist
/-- The Cauchy–Schwarz step 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 `π`,
`4‖Pⁿ(x, ·) − π‖²_Var ≤ (1/π(x)) P^{2n}(x, x) − 1` for every state `x` and every `n`. -/
theorem four_tvDist_sq_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 : ℕ), 4 * tvDist (rowDist P n x) π ^ 2 ≤ (P ^ (2 * n)) x x / π x - 1 := by sorry
end DiaconisStroock.VarDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.