Lemma 7.9 -- projections do not increase total variation
ProvedMarkovMixing.projection_lower_boundmarkov-chainsmixing-timesprobability
Let and be probability distributions on a finite state space , let be any map to a finite set , and write for the pushforward of along — the law of the statistic, . Let denote the total variation distance (on or on as appropriate).
The theorem (Lemma 7.9 of Levin–Peres–Wilmer) asserts that projecting can only lose information:
Consequently any lower bound on the distance between the projected laws — for instance one produced by the distinguishing-statistic inequality applied on — is automatically a lower bound on the distance between the original distributions. This is the step that turns observable-level separations into total-variation lower bounds for chains.
Preamble
import Definitions.Def_mm_lower
Formal statement
namespace MarkovMixing
/-- **Lemma 7.9** (LPW): projecting by a statistic `f : Ω → Λ` can only
decrease total variation distance:
`‖μ f⁻¹ − ν f⁻¹‖_TV ≤ ‖μ − ν‖_TV`. -/
theorem projection_lower_bound {V : Type*} [Fintype V] [DecidableEq V]
{Λ : Type*} [Fintype Λ] [DecidableEq Λ]
(μ ν : V → ℝ) (hμ : IsDist μ) (hν : IsDist ν) (f : V → Λ) :
tvDist (pushforward μ f) (pushforward ν f) ≤ tvDist μ ν := 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.3, Lemma 7.9, pp. 92-93