Section 4.5 -- standard mixing-time inequalities
ProvedMarkovMixing.mixing_time_epsmarkov-chainsmixing-timesprobability
Let be an irreducible, aperiodic 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. For a tolerance , the mixing time is the first time this distance drops to ,
The theorem asserts, for any tolerance , the two standard consequences of submultiplicativity (displays (4.34)–(4.36) of Levin–Peres–Wilmer). First, running the chain for blocks of length shrinks the distance geometrically:
Second, mixing to any tolerance costs only logarithmically many standard mixing times:
This is why the convention is harmless: any other tolerance changes the mixing time by at most a logarithmic factor.
Preamble
import Definitions.Def_mm_mixing import Mathlib.Analysis.SpecialFunctions.Log.Base
Formal statement
namespace MarkovMixing
/-- **§4.5, Eqs. (4.34)–(4.36)** (LPW): for an irreducible aperiodic chain,
`d(ℓ · t_mix(ε)) ≤ (2ε)^ℓ`, and consequently
`t_mix(ε) ≤ ⌈log₂ ε⁻¹⌉ · t_mix`. -/
theorem mixing_time_eps {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 π)
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) :
(∀ ℓ : ℕ, distStationary P π (ℓ * mixingTime P π ε) ≤ (2 * ε) ^ ℓ) ∧
mixingTime P π ε ≤ ⌈Real.logb 2 ε⁻¹⌉₊ * tMix P π := 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 4.5, Eqs. (4.34)-(4.36), p. 55