Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 9.1 — strong total-variation coefficient

Definition
DuchiSIT_TVContractionCoefficient

by Mrnaiq · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

information-theoryprobabilitytotal-variation

The real supremum of output total-variation distance divided by input total-variation distance, over all distinct input probability laws. The same Markov kernel is applied to both laws. Distinct probability laws have positive total-variation distance. Real division is total in Lean; proving that the ratios are bounded is part of the formalization. The spaces are arbitrary measurable spaces; no finite-state, topology, stationarity or irreducibility assumption is imposed. Real suprema use zero on an empty index set. The source notation is extended explicitly to empty spaces and spaces with at most one probability measure.

Definition code
import Definitions.Def_DuchiSIT_DobrushinCoefficient
set_option autoImplicit false
noncomputable section
open MeasureTheory ProbabilityTheory
namespace DuchiSIT

def tvContraction {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y]
    (K : Kernel X Y) [IsMarkovKernel K] : ℝ :=
  sSup {r : ℝ | ∃ μ ν : ProbabilityMeasure X, μ ≠ ν ∧
    r = MarkovChainCLT.tvDist (channel K μ : Measure Y) (channel K ν : Measure Y) /
      MarkovChainCLT.tvDist (μ : Measure X) (ν : Measure X)}

end DuchiSIT
Source
John Duchi, Lecture Notes on Statistics and Information Theory, December 6, 2023, Section 9.1, printed pp. 220–222, Definitions 9.1–9.2 and Proposition 9.1.1; total variation uses Lemma 2.2.4. https://web.stanford.edu/class/stats311/lecture-notes.pdf
Read-back

What the Lean code literally says, in plain math · gpt-6

For arbitrary types XXX and YYY, each equipped with a measurable space, and a Markov kernel KKK from XXX to YYY (so K(x)K(x)K(x) is a probability measure on YYY for every xxx, and its evaluations on measurable sets vary measurably with xxx), the definition assigns a real number c(K)c(K)c(K) as follows. For probability measures μ,ν\mu,\nuμ,ν on XXX, let μK\mu KμK be the probability measure whose value on a measurable set B⊆YB\subseteq YB⊆Y is ∫XK(x)(B) dμ(x)\int_X K(x)(B)\,d\mu(x)∫X​K(x)(B)dμ(x), and define νK\nu KνK likewise. For measures α,β\alpha,\betaα,β on a measurable space ZZZ, put DZ(α,β)=sup⁡A⊆Z, A measurable∣toReal⁡(α(A))−toReal⁡(β(A))∣D_Z(\alpha,\beta)=\sup_{A\subseteq Z,\ A\text{ measurable}} |\operatorname{toReal}(\alpha(A))-\operatorname{toReal}(\beta(A))|DZ​(α,β)=supA⊆Z, A measurable​∣toReal(α(A))−toReal(β(A))∣, where the supremum is taken in R\mathbb RR and toReal⁡\operatorname{toReal}toReal converts an extended nonnegative real to a real, sending +∞+\infty+∞ to 000. Then c(K)=sup⁡{DY(μK,νK)/DX(μ,ν):μ,ν are probability measures on X, μ≠ν}c(K)=\sup\{D_Y(\mu K,\nu K)/D_X(\mu,\nu):\mu,\nu\text{ are probability measures on }X,\ \mu\ne\nu\}c(K)=sup{DY​(μK,νK)/DX​(μ,ν):μ,ν are probability measures on X, μ=ν}, again a supremum in R\mathbb RR. Thus the outer set consists of all real ratios witnessed by two distinct probability measures, with no additional hypotheses on XXX, YYY, or their measurable spaces; in particular the quantifiers do not require the underlying types to be nonempty. These are real suprema, with the convention that the supremum of the empty set, or of a set not bounded above, is 000. In particular, if XXX admits no pair of distinct probability measures, the outer set is empty and c(K)=0c(K)=0c(K)=0. All measures evaluated in these ratios are probability measures, so their set evaluations are finite; distinct probability measures give DX(μ,ν)>0D_X(\mu,\nu)>0DX​(μ,ν)>0. The division is real division (whose total definition gives a/0=0a/0=0a/0=0, although a zero denominator does not occur for an admitted pair).

Human review
  • Endorsed by Shuze Chen · Nov 12, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Mrnaiq · Nov 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me