CommunicationComplexity.tvDistanceSup
defimported Lean
The supremum definition of total variation distance between $\mu$ and $\nu$ is \[ \mathrm{TV}_{\sup}(\mu,\nu) \;=\; \sup\bigl\{|\mu(S) - \nu(S)| : S \subseteq \Omega \text{ measurable}\bigr\}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in noncomputable def CommunicationComplexity.tvDistanceSup {Ω : Type*} [MeasurableSpace Ω] (μ ν : Measure Ω) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν] : ℝ
- Defined in
- TCSlib, `CommunicationComplexity.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.tvDistanceSup← CommunicationComplexity.tvDistanceSup (TCSlib/CommunicationComplexity/NewmanTheorem/TVDistance.lean:79): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 2
- CommunicationComplexity.tvDistanceSup_eq_densityPositiveIntegral_of_acTotal variation distance as the excess-mass integral. Let $\mu$ and $\nu$ be probability measures on a measurable space $\Omega$, and…
- CommunicationComplexity.TVDistance.tvDistance_eq_tvDistanceSupEquivalence of the two definitions of total variation distance. Let $\mu$ and $\nu$ be probability measures on a measurable space…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in /-- Total variation distance between probability measures, defined as the supremum over measurable events `S` of `|μ(S) − ν(S)|`. [LPW17, §4.1, eq. (4.1)] (statistical distance; also the `|p − q|` of [RY20, Lemma 6.6]). -/ noncomputable def CommunicationComplexity.tvDistanceSup {Ω : Type*} [MeasurableSpace Ω] (μ ν : Measure Ω) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν] : ℝ := sSup (Set.range fun S : {S : Set Ω // MeasurableSet S} => |μ.real (S : Set Ω) - ν.real (S : Set Ω)|)