Proposition 4.5 -- total variation via bounded test functions
ProvedMarkovMixing.tv_sup_functionsmarkov-chainsmixing-timesprobability
Let and be probability distributions on a finite state space , and let denote their total variation distance, the largest discrepancy in the probability of a single event. Write for the expectation of an observable under .
The theorem (Proposition 4.5 of Levin–Peres–Wilmer) characterizes the distance by expectations of bounded observables:
the supremum running over all functions on bounded by in absolute value. In words: two distributions are far in total variation exactly when some -valued statistic has visibly different means under the two.
Preamble
import Definitions.Def_mm_mixing
Formal statement
namespace MarkovMixing
/-- **Proposition 4.5** (LPW): the total variation distance equals half the
supremum, over functions bounded by `1` in absolute value, of the difference
of expectations. -/
theorem tv_sup_functions {V : Type*} [Fintype V] [DecidableEq V]
(μ ν : V → ℝ) (hμ : IsDist μ) (hν : IsDist ν) :
tvDist μ ν =
2⁻¹ * ⨆ f : {f : V → ℝ // ∀ x, |f x| ≤ 1},
|∑ x, (f : V → ℝ) x * μ x - ∑ x, (f : V → ℝ) x * ν x| := 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.1, Proposition 4.5, p. 49