Section 7.1.1 -- the counting bound
ProvedMarkovMixing.counting_lower_boundmarkov-chainsmixing-timesprobability
Let be an irreducible, aperiodic Markov chain on a finite state space whose stationary distribution is uniform. Let
be the maximal number of states reachable from a single state in one step. For a tolerance , the mixing time is the first with , where is the total variation distance.
The theorem (the counting bound, §7.1.1, display (7.2) of Levin–Peres–Wilmer) asserts: for every ,
The reason: in steps the chain can reach at most states, and until is comparable to the time- distribution misses most of a uniform target. In particular chains with bounded branching need at least steps to mix.
Preamble
import Definitions.Def_mm_lower import Mathlib.Analysis.SpecialFunctions.Log.Basic
Formal statement
namespace MarkovMixing
/-- **§7.1.1, Eq. (7.2)** (LPW), the counting bound: for a chain with uniform
stationary distribution, `t_mix(ε) ≥ log(|Ω|(1−ε)) / log Δ`, where `Δ` is
the maximal number of states accessible in one step. -/
theorem counting_lower_bound {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(hap : Aperiodic P) (hπ : IsStationary P (uniformDist V))
(ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1) :
Real.log ((Fintype.card V : ℝ) * (1 - ε)) / Real.log (maxOutDegree P) ≤
(mixingTime P (uniformDist V) ε : ℝ) := 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 7.1.1, Eq. (7.2), p. 87