Theorem 4.9 -- the Convergence Theorem
ProvedMarkovMixing.convergence_theoremLet be the transition matrix of an irreducible and aperiodic Markov chain on a finite state space — irreducible meaning every state can reach every other in some number of steps, aperiodic meaning the return times to a state have greatest common divisor one — and let be a stationary distribution for , i.e. for all . Write for the distribution of the chain at time started at , and for the total variation distance.
The theorem — the Convergence Theorem (Theorem 4.9 of Levin–Peres–Wilmer), the capstone of Chapter 4 — asserts that the chain converges to geometrically fast, uniformly in the starting state: there exist a rate and a constant such that
In particular the stationary distribution of an irreducible aperiodic chain is unique and is reached from every starting point, with an error decaying exponentially in time — the statement that gives the mixing time its meaning, and the result all later chapters quantify.
import Definitions.Def_mm_mixing
namespace MarkovMixing
/-- **Theorem 4.9, the Convergence Theorem** (LPW), the capstone of
Chapter 4: an irreducible, aperiodic finite chain converges to its stationary
distribution geometrically fast in total variation:
`max_x ‖P^t(x,·) − π‖_TV ≤ C αᵗ` for some `α ∈ (0,1)` and `C > 0`. -/
theorem convergence_theorem {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(hap : Aperiodic P) (π : V → ℝ) (hπ : IsStationary P π) :
∃ α : ℝ, α ∈ Set.Ioo (0 : ℝ) 1 ∧ ∃ C : ℝ, 0 < C ∧
∀ t : ℕ, distStationary P π t ≤ C * α ^ t := by
sorry
end MarkovMixing