Lemma 6.13 -- total variation is bounded by separation
ProvedMarkovMixing.tv_le_sepmarkov-chainsmixing-timesprobability
Let be a Markov chain on a finite state space with strictly positive stationary distribution . Write for the distribution at time started at , for the total variation distance, and
for the separation distance at time from the starting state .
The theorem (Lemma 6.13 of Levin–Peres–Wilmer) asserts that separation dominates total variation: for every starting state and every time ,
Consequently any bound on the separation distance — for instance one obtained from a strong stationary time — is automatically a bound on the total variation distance to stationarity.
Preamble
import Definitions.Def_mm_stopping
Formal statement
namespace MarkovMixing
/-- **Lemma 6.13** (LPW): total variation distance to stationarity is bounded
by the separation distance: `‖P^t(x,·) − π‖_TV ≤ s_x(t)`. -/
theorem tv_le_sep {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P)
(π : V → ℝ) (hπ : IsStationary P π) (hpos : ∀ y : V, 0 < π y)
(x : V) (t : ℕ) :
tvDist (rowDist P t x) π ≤ sepDist P π x 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, Lemma 6.13, p. 80