Mutual information with a k-valued variable is at most
ProvedInformationTheory.finite_range_mutualInformation_le_log_cardentropyinformation-theorymutual-information
Let and be random variables on a common probability space, where takes values in a nonempty set of elements. Their mutual information, defined as relative entropy of the joint law from the product of the marginals, obeys
No finiteness assumption is imposed on the range of .
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
theorem InformationTheory.finite_range_mutualInformation_le_log_card
{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 (Measure.map (fun x ↦ (f x, g x)) mu)
((Measure.map f mu).prod (Measure.map g mu))).toReal ≤ Real.log k := 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: total information about the k-valued optimal action is at most the log k diameter of negentropy.