Finite-valued conditional KL is bounded by marginal entropy
ProvedInformationTheory.compProd_categorical_kl_le_marginal_entropy_generalbanditsinformation-theoryprobability
Let be a probability measure on an arbitrary measurable space , let be a Markov kernel from to a finite action set , and put . Then
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 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.