Proposition 4.7 -- the coupling characterization of total variation
ProvedMarkovMixing.tv_couplingLet and be probability distributions on a finite state space , and let denote their total variation distance. A coupling of and is a probability distribution on ordered pairs whose marginals are and — that is, for every and for every ; one thinks of as the joint law of a pair of random variables with and .
The theorem (Proposition 4.7 and Remark 4.8 of Levin–Peres–Wilmer) asserts two things. First, every coupling places at least of its mass off the diagonal:
Second, some coupling attains this bound — an optimal coupling, whose off-diagonal mass is exactly . Together: the total variation distance is the minimal probability of disagreement achievable by any joint realization of the two distributions, and the minimum is attained.
import Definitions.Def_mm_mixing
namespace MarkovMixing
/-- **Proposition 4.7 and Remark 4.8** (LPW): every coupling `(X,Y)` of `μ`
and `ν` has `P{X ≠ Y} ≥ ‖μ − ν‖_TV`, and there is an *optimal* coupling
attaining equality. -/
theorem tv_coupling {V : Type*} [Fintype V] [DecidableEq V]
(μ ν : V → ℝ) (hμ : IsDist μ) (hν : IsDist ν) :
(∀ q : V × V → ℝ, IsCoupling μ ν q →
tvDist μ ν ≤ ∑ p ∈ Finset.univ.filter (fun p : V × V => p.1 ≠ p.2), q p) ∧
∃ q : V × V → ℝ, IsCoupling μ ν q ∧
tvDist μ ν = ∑ p ∈ Finset.univ.filter (fun p : V × V => p.1 ≠ p.2), q p := by
sorry
end MarkovMixing