Bretagnolle–Huber inequality on a finite type in any universe
ProvedBanditAlgorithm.bretagnolle_huber_inequality_finite_typeStarbanditsinformation-theoryprobabilitytextbook
Let and be probability measures on a finite measurable space , where the carrier type may live in any Lean universe. For every measurable event , if , then
This is the Bretagnolle–Huber testing inequality. The universe-polymorphic finite-space form is useful for finite histories whose signal type is declared in an arbitrary universe.
Formalization Note This has the same mathematical conclusion as the existing platform theorem BanditAlgorithm.bretagnolle_huber_inequality; it adds a finite-carrier hypothesis so that an arbitrary-universe carrier can be measurably reindexed by a universe-zero type and the existing theorem reused.
Preamble
import Theorems.Thm_BanditAlgorithm_bretagnolle_huber_inequality import Theorems.Thm_InformationTheory_klDiv_map_measurableEmbedding import Mathlib.Data.Fintype.EquivFin open MeasureTheory InformationTheory Real open scoped ENNReal
Formal statement
theorem BanditAlgorithm.bretagnolle_huber_inequality_finite_typeStar
{Ω : Type*} [Fintype Ω] {mΩ : MeasurableSpace Ω}
(P Q : Measure Ω) [IsProbabilityMeasure P] [IsProbabilityMeasure Q]
{A : Set Ω} (hA : MeasurableSet A) (hD : klDiv P Q ≠ ∞) :
2⁻¹ * exp (-(klDiv P Q).toReal) ≤ P.real A + Q.real Aᶜ := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 14.2, printed pp. 190–191. This is a universe-polymorphic finite-space restatement of the existing platform formalization.