Lemma 4.12 -- submultiplicativity of
ProvedMarkovMixing.distPairs_submultiplicativemarkov-chainsmixing-timesprobability
Let be any stochastic matrix on a finite state space (nonnegative entries, rows summing to one), write for the row of the -th matrix power — the distribution at time of the chain started at — and let
be the worst pairwise total variation distance between two copies of the chain at time .
The theorem (Lemma 4.12 of Levin–Peres–Wilmer) asserts that is submultiplicative:
No irreducibility or aperiodicity is needed. Combined with the comparison to the distance to stationarity, submultiplicativity is what makes distances decay geometrically past the mixing time, and hence what makes the mixing time a meaningful single parameter of a chain.
Preamble
import Definitions.Def_mm_mixing
Formal statement
namespace MarkovMixing
/-- **Lemma 4.12** (LPW): `d̄` is submultiplicative:
`d̄(s + t) ≤ d̄(s) · d̄(t)`. -/
theorem distPairs_submultiplicative {V : Type*} [Fintype V] [DecidableEq V]
[Nonempty V] (P : Matrix V V ℝ) (hP : IsStochastic P) (s t : ℕ) :
distPairs P (s + t) ≤ distPairs P s * distPairs 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.12, p. 54