Mutual information is at most marginal entropy
ProvedInformationTheory.finite_range_mutualInformation_le_marginal_entropyentropyinformation-theorymutual-information
Let and be random variables on a common probability space, with taking values in the finite set . If , then
This is the standard fact that observing cannot reveal more information about than the entropy initially present in .
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic import Mathlib.Analysis.SpecialFunctions.Log.NegMulLog open MeasureTheory ProbabilityTheory InformationTheory open scoped BigOperators
Formal statement
theorem InformationTheory.finite_range_mutualInformation_le_marginal_entropy
{Omega Alpha : Type} {mOmega : MeasurableSpace Omega}
{mAlpha : MeasurableSpace Alpha} {k : ℕ}
(mu : Measure Omega) [IsProbabilityMeasure mu]
(f : Omega → Alpha) (g : Omega → Fin k)
(hf : Measurable f) (hg : Measurable g) :
(klDiv (Measure.map (fun x ↦ (f x, g x)) mu)
((Measure.map f mu).prod (Measure.map g mu))).toReal ≤
∑ a, Real.negMulLog ((Measure.map g mu).real {a}) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed p. 471 (PDF p. 480), proof of Theorem 36.5: information learned about the optimal action is bounded by its entropy; the entropy is then bounded by log k.