Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite-valued conditional KL is bounded by marginal entropy

Proved
InformationTheory.compProd_categorical_kl_le_marginal_entropy_general

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

banditsinformation-theoryprobability

Let μ\muμ be a probability measure on an arbitrary measurable space X\mathcal XX, let κ\kappaκ be a Markov kernel from X\mathcal XX to a finite action set [k][k][k], and put p=μκp=\mu\kappap=μκ. Then

D ⁣(μ⊗κ ∥ μ⊗p)  ≤  H(p)=∑a∈[k]−p(a)log⁡p(a).D\!\left(\mu\otimes\kappa\,\middle\|\,\mu\otimes p\right) \;\le\; H(p) =\sum_{a\in[k]}-p(a)\log p(a).D(μ⊗κ∥μ⊗p)≤H(p)=a∈[k]∑​−p(a)logp(a).

This is the conditional-kernel form of the fact that information carried by a finite-valued variable is bounded by its entropy. The source measurable space needs no regularity beyond what is required to define the kernel.

Formalization Note The independent coupling μ⊗p\mu\otimes pμ⊗p is represented by a composition-product with a constant kernel.

Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic
import Mathlib.Analysis.SpecialFunctions.Log.NegMulLog
import Mathlib.Probability.Kernel.Composition.MeasureCompProd

open MeasureTheory ProbabilityTheory InformationTheory
open scoped ENNReal BigOperators ProbabilityTheory
Formal statement
namespace InformationTheory

theorem compProd_categorical_kl_le_marginal_entropy_general
    {Alpha : Type} {mAlpha : MeasurableSpace Alpha}
    {k : ℕ} [NeZero k] (mu : Measure Alpha) [IsProbabilityMeasure mu]
    (kappa : Kernel Alpha (Fin k)) [IsMarkovKernel kappa] :
    (klDiv (mu ⊗ₘ kappa)
      (mu ⊗ₘ Kernel.const Alpha (kappa ∘ₘ mu))).toReal ≤
      ∑ a, Real.negMulLog ((kappa ∘ₘ mu).real {a}) := by
  sorry

end InformationTheory
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), printed pp. 470–471, Theorem 36.6 and Lemma 36.7, https://tor-lattimore.com/downloads/book/book.pdf; conditional-kernel form of the finite-alphabet entropy step.

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