Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Mutual information with a finite-valued variable is finite

Proved
InformationTheory.finite_range_mutualInformation_ne_top

by Harry_Xu · Aug 2, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsinformation-theoryrelative-entropy

Let μ\muμ be a probability measure, let FFF be a measurable random variable with arbitrary measurable codomain, and let GGG be a measurable random variable taking values in the nonempty finite set {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}. Then the mutual information between FFF and GGG is finite:

D ⁣(Lμ(F,G) ∥ Lμ(F)⊗Lμ(G))<∞.D\!\left(\mathcal L_\mu(F,G)\,\middle\|\,\mathcal L_\mu(F)\otimes\mathcal L_\mu(G)\right)<\infty.D(Lμ​(F,G)∥Lμ​(F)⊗Lμ​(G))<∞.

This finiteness lemma permits conversion of the extended-real mutual information to a real number in finite-action information-ratio arguments.

Formalization Note The conclusion is expressed as non-equality to ∞\infty∞ for Lean’s extended nonnegative real-valued Kullback–Leibler divergence.

Preamble
import Theorems.Thm_InformationTheory_klDiv_compProd_self_eq_lintegral_of_ae
import Theorems.Thm_InformationTheory_klDiv_map_measurableEmbedding
import Theorems.Thm_InformationTheory_finite_range_mutualInformation_le_marginal_entropy
import Theorems.Thm_InformationTheory_categorical_toReal_klDiv_eq_sum
import Mathlib.InformationTheory.KullbackLeibler.ChainRule
import Mathlib.Probability.Kernel.CondDistrib
import Mathlib.Probability.Kernel.Composition.AbsolutelyContinuous

open MeasureTheory ProbabilityTheory InformationTheory
open scoped ENNReal ProbabilityTheory

namespace InformationTheory
Formal statement
theorem finite_range_mutualInformation_ne_top
    {Omega Alpha : Type*} {mOmega : MeasurableSpace Omega}
    {mAlpha : MeasurableSpace Alpha} {k : ℕ} [NeZero k]
    (mu : Measure Omega) [IsProbabilityMeasure mu]
    (f : Omega → Alpha) (g : Omega → Fin k)
    (hf : Measurable f) (hg : Measurable g) :
    klDiv (mu.map (fun x ↦ (f x, g x)))
      ((mu.map f).prod (mu.map g)) ≠ ∞ := by sorry
Source
Lattimore and Szepesvari, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 / free PDF p. 479; standard bound I(F;G) <= H(G) <= log k.

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