§1D, proof of Proposition 3, p. 42 — reversibility identity P^{2n}(x,x)/π(x) = Σ_y Pⁿ(x,y)²/π(y)
ProvedDiaconisStroock.VarDist.pow_two_mul_diag_div_eqLet be a finite set and the transition matrix of an irreducible Markov chain on , reversible with respect to its stationary probability distribution : for all . Write for the -step transition probabilities. Then for every state and every ,
This identity turns the -type sum produced by the Cauchy–Schwarz step in the proof of Proposition 3 into a single diagonal entry of , which can then be controlled spectrally.
Formalization Note The chain is a real matrix P with IsStochastic P, irreducibility is MarkovMixing.Irreducible P (every state reaches every state), IsStationary P π says is a probability vector with , and DetailedBalance P π is reversibility. Irreducibility and stationarity together give for all ("π charges every point", §1A), so the divisions are by positive numbers; no positivity hypothesis is added. The case is included (both sides equal ).
import Mathlib import Definitions.Def_mm_basic open MarkovMixing
namespace DiaconisStroock.VarDist
/-- The reversibility identity 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 `π`,
`(1/π(x)) P^{2n}(x, x) = ∑_y (Pⁿ(x, y))² / π(y)` for every state `x` and every `n`. -/
theorem pow_two_mul_diag_div_eq {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 = ∑ y, ((P ^ n) x y) ^ 2 / π y := by sorry
end DiaconisStroock.VarDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.