Section 7.1.2 -- the diameter bound
ProvedMarkovMixing.diameter_lower_boundLet be an irreducible, aperiodic Markov chain on a finite state space with stationary distribution . The transition graph of joins two distinct states whenever the chain can cross between them in one step in either direction ( or ); write for the graph distance in this graph — the least number of steps needed to travel from to . For a tolerance , the mixing time is the first with , where .
The theorem (the diameter bound, §7.1.2, display (7.3) of Levin–Peres–Wilmer) asserts: for every tolerance and every pair of states ,
Equivalently, the mixing time is at least half the diameter of the transition graph: started at two states at distance , for the two time- distributions occupy disjoint balls and cannot both be within of the same .
import Definitions.Def_mm_lower
namespace MarkovMixing
/-- **§7.1.2, Eq. (7.3)** (LPW), the diameter bound: for `ε < 1/2`, the
mixing time is at least half the graph distance between any two states (in
particular, at least half the diameter of the chain). -/
theorem diameter_lower_bound {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ε2 : ε < 1 / 2) (x₀ y₀ : V) :
(transGraph P).dist x₀ y₀ ≤ 2 * mixingTime P π ε := by
sorry
end MarkovMixing