A randomized data-processing procedure can reduce the statistical difference between two input populations. The same mathematical question appears when a Markov chain updates two possible initial distributions: how much of their original distinguishability remains after one transition? A qualitative statement that processing cannot increase total variation answers only part of the question. A quantitative contraction coefficient describes the largest fraction of the difference that can survive the channel, uniformly over all input distributions. The connection between these coefficients and geometric mixing is developed in John Duchi's Lecture Notes on Statistics and Information Theory, Section 9.1.
The target here is the exact total-variation coefficient, rather than an unspecified upper bound. It connects a quantity defined by pairs of individual input states to a quantity defined by arbitrary pairs of input probability distributions. Both descriptions are useful: one exposes the transition rule, while the other describes its effect on statistical comparisons.
Let X and Y be measurable spaces. A probability law on X assigns total mass one to X. A Markov kernel K from X to Y assigns a probability law K(x,·) on Y to each input state x, with measurable dependence on x for every measurable output event. A kernel is therefore the mathematical representation of a randomized channel with input space X and output space Y. Neither space is restricted to a finite set.
For probability laws μ and ν on the same space, their total-variation distance is
This is the normalization in which the distance lies between zero and one. It agrees with the event characterization in Lemma 2.2.4 of the source notes, rather than the doubled signed-measure norm used in some references. The formalization reuses the existing platform definition MarkovChainCLT.tvDist; on probability measures all of its event evaluations are finite.
The output law Kμ is determined by
for measurable output events B. This operation is called channel in the Lean development. Its output is again a probability law, so the same total-variation distance applies before and after processing.
The Dobrushin coefficient is the largest distance between two rows of the channel:
Definition 9.2 in the source notes introduces this coefficient. The strong total-variation data-processing coefficient compares arbitrary distinct input laws:
The mission goal is Proposition 9.1.1, printed pages 221–222 of the December 6, 2023 version:
Two milestones retain the two directions identified in that proposition. The contraction milestone states, for every pair of input probability laws,
The sharpness milestone states
Together these targets identify the coefficient itself, including channels whose coefficient is zero or one. The goal is not merely nonexpansion with coefficient one.
The equality makes the row-based and distribution-based descriptions interchangeable. It provides a common interface for later work on mixing, statistical information loss, and composition of randomized procedures. It also separates a property of an individual channel from the choice of an initial law. A future application can establish an upper bound on the same coefficient without replacing the theorem by an application-specific statement.
The mathematical result is known. The remaining task is a machine-checked development of this exact statement in the common probability-measure and kernel interface. An existing proved finite-vector nonexpansion theorem is included as an adjacent reference. It is not a proof of this general kernel result and is not assumed as a substitute for either milestone. This mission does not claim that a new mathematical theorem has been discovered.
Finite stochastic matrices permit calculations with finite sums. A general measurable-space kernel requires the argument to account for arbitrary probability laws and arbitrary measurable events. A proof restricted to finitely supported inputs would leave part of the stated quantifier range uncovered. There is also a distinction between finding a valid contraction bound and showing that its constant equals the row coefficient. Both directions of the displayed equality are required.
The operational definitions must remain genuine: the coefficient cannot be defined to equal the desired optimum. The row supremum and the distribution-ratio supremum are separate definitions. Their equality is the theorem to be proved.
The development uses Mathlib's measurable spaces, bundled ProbabilityMeasure types, Markov kernels, and the IsMarkovKernel typeclass. Kernel action is actual measure composition. The three new definition modules cover channel action, the row coefficient, and the ratio coefficient. All declarations share the book-wide namespace DuchiSIT. No irreducibility, stationarity, finite-state assumption, topology, or finite-support restriction is added.
The coefficients are real suprema. On probability inputs the relevant quantities are bounded; proving the bounds needed to use these suprema is part of the formal work. Lean's real supremum of an empty set is zero. Consequently a space admitting at most one probability law has ratio coefficient zero. Empty input spaces are also included by this zero convention; this is an explicit total extension of the source notation. Distinct probability measures have positive total-variation distance, so ratios in the nonempty index set do not require division by zero. Real division remains total in the definitions and must not be used to conceal a missing positivity argument.
Contributions are welcome on the two milestones, on reusable measure-theoretic support results, and on the final equality. New statements should reuse these definitions and the existing total-variation foundation. The draft theorems contain open proof placeholders. Local compilation has not been completed because the precompiled Mathlib cache was unavailable in the drafting environment. Platform compilation and statement review remain required before launch; no proof of the goal or milestones is claimed.
namespace DuchiSIT
theorem dobrushin_eq_tvContraction {X Y : Type*}
[MeasurableSpace X] [MeasurableSpace Y]
(K : Kernel X Y) [IsMarkovKernel K] :
dobrushin K = tvContraction K := by sorry
end DuchiSIT
For every Markov kernel between arbitrary measurable spaces, its Dobrushin row coefficient equals its strong total-variation data-processing coefficient. Both coefficients are independently defined using the same event-supremum total-variation normalization. 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.
No open leaves. Every sub-goal is proved or awaiting decomposition.