Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Data-processing inequality for the trade-off function

Proved
StatUnlearn.tof_le_tof_comp

by 2017Advanced@ · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

hypothesis-testingmeasure-theoryprobabilitystatistics

Let κ\kappaκ be a Markov kernel from a measurable space WWW to a measurable space VVV, let P,QP,QP,Q be probability distributions on WWW, and let κ∗P\kappa_*Pκ∗​P, κ∗Q\kappa_*Qκ∗​Q be their images under κ\kappaκ. Then for every type-I level t≥0t\ge0t≥0,

T(P,Q)(t) ≤ T(κ∗P, κ∗Q)(t).T(P,Q)(t)\ \le\ T(\kappa_*P,\ \kappa_*Q)(t).T(P,Q)(t) ≤ T(κ∗​P, κ∗​Q)(t).

Post-processing cannot make two distributions easier to tell apart: a test φ\varphiφ on the output space pulls back to the test w↦∫φ dκ(w)w\mapsto\int\varphi\,d\kappa(w)w↦∫φdκ(w) on the input space, with exactly the same type-I and type-II errors, so every error pair achievable for the post-processed distributions is already achievable for the originals and the infimum over the larger set is no larger.

This is the data-processing inequality for trade-off functions, the direction of Blackwell's theorem that governs every information-theoretic statement in the paper: it converts "κ\kappaκ maps one experiment to another" into an inequality between trade-off functions, and it is what makes the Gaussian baselines comparable in Proposition 3.1 and Proposition 2.1.

Preamble
import Mathlib.Probability.Kernel.Composition.IntegralCompProd
import Mathlib.Probability.Kernel.Composition.CompNotation
import Mathlib.MeasureTheory.Measure.MeasureSpaceDef
import Definitions.Def_su_tof
open MeasureTheory ProbabilityTheory
Formal statement
namespace StatUnlearn

theorem tof_le_tof_comp {W V : Type*} [MeasurableSpace W] [MeasurableSpace V]
    (κ : Kernel W V) [IsMarkovKernel κ] (P Q : Measure W) [IsProbabilityMeasure P]
    [IsProbabilityMeasure Q] (t : ℝ) (ht : 0 ≤ t) :
    tof P Q t ≤ tof (κ ∘ₘ P) (κ ∘ₘ Q) t := by
  sorry

end StatUnlearn
Source
Pandey, Kulkarni, "Statistical Unlearning of Distributions: A Hypothesis Testing Approach", arXiv:2605.16645, Theorem A.4 (`thm:Blackwell`), data-processing direction; used in `proof:CoD` and `proof:FRP`

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