Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integrability of conditional mutual information with a finite coordinate

Proved
InformationTheory.conditional_finite_mutualInformation_integrable

by Harry_Xu · Aug 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditsconditional-mutual-informationinformation-theoryprobability

Let μ\muμ be a probability measure, let HHH and YYY be standard Borel spaces, and let AAA take values in the finite set [k][k][k]. For measurable random variables H(ω)H(\omega)H(ω), Y(ω)Y(\omega)Y(ω), and A(ω)A(\omega)A(ω), write μhA,Y\mu_h^{A,Y}μhA,Y​, μhA\mu_h^AμhA​, and μhY\mu_h^YμhY​ for their regular conditional laws given H=hH=hH=h. Then the conditional mutual-information density is integrable:

h⟼D ⁣(μhA,Y ∥ μhA⊗μhY)∈L1(μH).h\longmapsto D\!\left(\mu_h^{A,Y}\,\middle\|\,\mu_h^A\otimes\mu_h^Y\right)\in L^1(\mu_H).h⟼D(μhA,Y​​μhA​⊗μhY​)∈L1(μH​).

This finite-coordinate result supplies the measurability and integrability needed to use conditional information gains in information-ratio arguments.

Formalization Note The proof represents the density as an integral of categorical posterior divergences and bounds it by the entropy of a distribution on [k][k][k].

Preamble
import Mathlib.Probability.Kernel.CondDistrib
import Mathlib.InformationTheory.KullbackLeibler.Basic

open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
namespace InformationTheory

/-- Conditional mutual information is integrable when one coordinate takes
values in a finite type. -/
theorem conditional_finite_mutualInformation_integrable
    {Omega H Y : Type} {mOmega : MeasurableSpace Omega}
    {mH : MeasurableSpace H} {mY : MeasurableSpace Y}
    [StandardBorelSpace H] [StandardBorelSpace Y] [Nonempty Y]
    {k : ℕ} [NeZero k]
    (mu : Measure Omega) [IsProbabilityMeasure mu]
    (hist : Omega → H) (obs : Omega → Y) (act : Omega → Fin k)
    (hhist : Measurable hist) (hobs : Measurable obs) (hact : Measurable act) :
    Integrable
      (fun h ↦ (klDiv (condDistrib (fun w ↦ (act w, obs w)) hist mu h)
        ((condDistrib act hist mu h).prod (condDistrib obs hist mu h))).toReal)
      (mu.map hist) := by
  sorry

end InformationTheory
Source
Lattimore and Szepesvari, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 / free PDF p. 479; measure-theoretic finite-posterior integrability bridge used to formalize its conditional mutual information.

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