Lemma 4.11 -- comparing and
ProvedMarkovMixing.dist_le_distPairsmarkov-chainsmixing-timesprobability
Let be the transition matrix of a Markov chain on a finite state space with stationary distribution (that is, for all ), and write for the distribution of the chain at time started at , and for the total variation distance. Chapter 4 of Levin–Peres–Wilmer measures convergence by two quantities: the worst-case distance to stationarity and the worst pairwise distance,
The theorem (Lemma 4.11) asserts that for every time these are equivalent up to a factor of two:
The left inequality holds because is an average of the rows ; the right is the triangle inequality through . The point of is that, unlike , it is submultiplicative — the subject of the companion lemma.
Preamble
import Definitions.Def_mm_mixing
Formal statement
namespace MarkovMixing
/-- **Lemma 4.11** (LPW): `d(t) ≤ d̄(t) ≤ 2 d(t)`. -/
theorem dist_le_distPairs {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(P : Matrix V V ℝ) (hP : IsStochastic P)
(π : V → ℝ) (hπ : IsStationary P π) (t : ℕ) :
distStationary P π t ≤ distPairs P t ∧
distPairs P t ≤ 2 * distStationary P π 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 4.4, Lemma 4.11, p. 53