Proposition 6.10 -- the strong stationary time bound
ProvedMarkovMixing.strong_stationary_boundmarkov-chainsmixing-timesprobability
Let be an irreducible Markov chain on a finite state space with stationary distribution . Write for the distribution at time started at , for the total variation distance, and for the worst-case distance to stationarity. A strong stationary time for the chain started at is a randomized stopping rule that stops in finite time almost surely, with the stopped state distributed exactly as and independent of the stopping time.
The theorem (Proposition 6.10 of Levin–Peres–Wilmer) asserts: if a single stopping rule is a strong stationary time from every starting state, then for every time
To bound the mixing time of a chain it therefore suffices to construct one strong stationary time and control its tail uniformly in the start.
Preamble
import Definitions.Def_mm_stopping
Formal statement
namespace MarkovMixing
/-- **Proposition 6.10** (LPW): if `τ` is a strong stationary time from every
starting state, then `d(t) ≤ max_x P_x{τ > t}`. -/
theorem strong_stationary_bound {V : Type*} [Fintype V] [DecidableEq V]
[Nonempty V] (P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(π : V → ℝ) (hπ : IsStationary P π)
(s : ∀ t : ℕ, (Fin (t + 1) → V) → ℝ)
(hs : ∀ x : V, IsStrongStationaryTime P π x s) (t : ℕ) :
distStationary P π t ≤ ⨆ x : V, stopTailProb P x s t := by
sorry
end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 6.4, Proposition 6.10, p. 79