CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup
theoremverifiedimported Lean
Equivalence of the two definitions of total variation distance. Let $\mu$ and $\nu$ be probability measures on a measurable space $\Omega$. Then the total variation distance $\mathrm{TV}(\mu,\nu) = \tfrac{1}{2}\norm{\mu-\nu}_{\mathrm{TV}}$, defined as half the total variation norm of the signed measure $\mu-\nu$, agrees with its supremum form over events, \[ \mathrm{TV}(\mu,\nu) \;=\; \sup\bigl\{\,\abs{\mu(S)-\nu(S)} : S \subseteq \Omega \text{ measurable}\,\bigr\}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open Classical in theorem CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup {Ω : Type*} [MeasurableSpace Ω] (μ ν : Measure Ω) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν] : tvDistance μ ν = tvDistanceSup μ ν
- Source
- TCSlib, `CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup← CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup (TCSlib/CommunicationComplexity/NewmanTheorem/TVDistance.lean:238): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- CommunicationComplexity.tvDistanceSupThe supremum definition of total variation distance between $\mu$ and $\nu$ is…
- CommunicationComplexity.TVDistance.event_abs_measureReal_sub_le_half_totalVariationProbability gap bounded by half total variation. Let $\mu$ and $\nu$ be probability measures on a measurable space $\Omega$, and let…
- CommunicationComplexity.tvDistanceThe total variation distance between two probability measures $\mu$ and $\nu$ on $\Omega$ is defined as $\tfrac{1}{2}$ times the…
- CommunicationComplexity.signedMeasureDiffGiven two probability measures $\mu$ and $\nu$ on a measurable space $\Omega$, the signed measure difference $\mu - \nu$ is the…
- CommunicationComplexity.TVDistance.exists_event_abs_measureReal_sub_eq_half_totalVariationAttainment of the total-variation distance. Let $\mu$ and $\nu$ be probability measures on a measurable space $\Omega$, and let…
- Used by 1
- CommunicationComplexity.tvDistance_eq_densityPositiveIntegral_of_acTotal variation distance as an integral of density excess. Let $\mu$ and $\nu$ be probability measures on a measurable space $\Omega$, and…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen Classical in/-- The total-variation-mass definition agrees with the supremum-over-events definition: `½ ‖μ − ν‖ = sup_S |μ(S) − ν(S)|` over measurable events `S`. [LPW17, §4.1, eq. (4.1) and Prop. 4.2] (LPW take the supremum as the definition and prove, in the finite case, that it is half the `ℓ¹` norm; here the identification goes through the Jordan/Hahn decomposition and holds on any measurable space). **Proof sketch.** Write `μ − ν = P − N` for the Jordan decomposition; then `P(Ω) = N(Ω)`, so half the total variation mass is `P(Ω)`. Step 1 (upper bound): for every event `S`, `|μ(S) − ν(S)| = |P(S) − N(S)| ≤ P(Ω)`, hence the supremum is at most `P(Ω)`. Step 2 (attained): the complement of a Hahn negative set carries all of `P` and none of `N`, so its gap is exactly `P(Ω)`; hence `P(Ω)` is at most the supremum. Conclude by antisymmetry. -/theorem CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSup {Ω : Type*} [MeasurableSpace Ω] (μ ν : Measure Ω) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν] : tvDistance μ ν = tvDistanceSup μ ν := by let rhs : ℝ := (1 / 2 : ℝ) * (signedMeasureDiff μ ν).totalVariation.real Set.univ -- Step 1: every event gap is at most half the total variation mass have hset_le (S : {S : Set Ω // MeasurableSet S}) : |μ.real (S : Set Ω) - ν.real (S : Set Ω)| ≤ rhs := by simpa [rhs] using event_abs_measureReal_sub_le_half_totalVariation μ ν S have hrhs_nonneg : 0 ≤ rhs := by dsimp [rhs] positivity have hupper : tvDistanceSup μ ν ≤ rhs := by rw [tvDistanceSup] exact Real.sSup_le (by rintro _ ⟨S, rfl⟩; exact hset_le S) hrhs_nonneg -- Step 2: the Hahn-decomposition event attains it obtain ⟨Smax, hSmax⟩ := exists_event_abs_measureReal_sub_eq_half_totalVariation μ ν have hbdd : BddAbove (Set.range fun S : {S : Set Ω // MeasurableSet S} => |μ.real (S : Set Ω) - ν.real (S : Set Ω)|) := by exact ⟨rhs, by rintro _ ⟨S, rfl⟩; exact hset_le S⟩ have hlower : rhs ≤ tvDistanceSup μ ν := by rw [tvDistanceSup] dsimp [rhs] rw [← hSmax] exact le_csSup hbdd (Set.mem_range_self Smax) rw [tvDistance] exact le_antisymm (by simpa [rhs] using hlower) (by simpa [rhs] using hupper)