BanditAlgorithm.pinsker_inequality_total_variation
Proved(Pinsker, event form Eq. (14.13)) For probability measures on with klDiv P Q finite and any measurable :
This is the bandit-usable form of Pinsker's inequality (Eq. (14.12))
the sup-form follows by instantiating the theorem at and rearranging with , so no expressiveness is lost. BOUNDARY: the hypothesis is REQUIRED — at the junk value (∞).toReal = 0 makes the left-hand side , but can be (e.g. , , ). The book's form is trivially true at .
import Mathlib.InformationTheory.KullbackLeibler.Basic open MeasureTheory InformationTheory Real open scoped ENNReal
theorem BanditAlgorithm.pinsker_inequality_total_variation {Ω : Type} {mΩ : MeasurableSpace Ω}
(P Q : Measure Ω) [IsProbabilityMeasure P] [IsProbabilityMeasure Q]
{A : Set Ω} (hA : MeasurableSet A) (hD : klDiv P Q ≠ ∞) :
1 - Real.sqrt ((klDiv P Q).toReal / 2) ≤ P.real A + Q.real Aᶜ := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. Let be an arbitrary measurable space, two probability measures on it, and a measurable set. Here denotes the library's Kullback–Leibler divergence: when is absolutely continuous with respect to and the log-likelihood ratio is -integrable, is the image in of the real integral (a negative value — impossible for probability measures — would be truncated to ); in every other case . Assume and write for its finite real value. Write and for the real-valued measures of and of its complement (finite, since both are probability measures).
Assertion. As an inequality between real numbers,
Hypotheses:
- and are both probability measures on the same measurable space .
- is a measurable subset of (the claim is universally quantified over such ).
- — in particular with -integrable log-likelihood ratio.
Edge cases and caveats:
- is the real square root ( on negative inputs); its argument is nonnegative since the divergence lies in .
- When the left-hand side is and the inequality holds trivially from nonnegativity of measures; the statement's content is confined to , though it is asserted for all finite .
- is obtained from the extended-real divergence by the conversion sending to ; the finiteness hypothesis blocks that junk case (without it, at the left side would evaluate to , the strongest possible claim).
- The statement is a per-event bound on the sum for one measurable set at a time; no total-variation distance object appears in it.
- The inequality is non-strict.
Confirmed by the mission captain (proposal self-audit).