Proposition 4.2 -- total variation as half the distance
ProvedMarkovMixing.tv_eq_half_l1markov-chainsmixing-timesprobability
Let and be probability distributions on a finite state space , and let
denote their total variation distance — the largest discrepancy the two distributions assign to a single event.
The theorem gives the two standard closed forms for this distance (Proposition 4.2 and Remark 4.3 of Levin–Peres–Wilmer). First, it is half the distance between the mass functions:
Second, it equals the total excess of over on the set where dominates:
i.e. the maximum in the definition is attained at the event .
Preamble
import Definitions.Def_mm_mixing
Formal statement
namespace MarkovMixing
/-- **Proposition 4.2 and Remark 4.3** (LPW): the total variation distance is
half the `ℓ¹` distance, and equals the excess of `μ` over `ν` on the set
where `μ ≥ ν`. -/
theorem tv_eq_half_l1 {V : Type*} [Fintype V] [DecidableEq V]
(μ ν : V → ℝ) (hμ : IsDist μ) (hν : IsDist ν) :
tvDist μ ν = 2⁻¹ * ∑ x, |μ x - ν x| ∧
tvDist μ ν = ∑ x ∈ Finset.univ.filter (fun x : V => ν x ≤ μ x), (μ 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.2 and Remark 4.3, p. 48
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.