Conditional finite-valued KL divergence is bounded by marginal entropy
ProvedInformationTheory.compProd_categorical_kl_le_marginal_entropybanditsinformation-theoryprobability
Let be a probability measure on a standard Borel space , let be a Markov kernel from to a finite action set , and put . The joint law and the independent coupling satisfy
This is the conditional-kernel form of the standard fact that mutual information with a finite-valued random variable is bounded by that variable’s entropy. It is designed for reuse when a joint law is represented by a regular conditional distribution.
Formalization Note The second measure is expressed as a composition-product with a constant kernel, and KL divergence is converted from extended nonnegative reals only after finiteness is established.
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
{Alpha : Type} {mAlpha : MeasurableSpace Alpha}
[StandardBorelSpace Alpha] [Nonempty 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 entropy step.