Entropy of a finite probability vector is at most
ProvedBanditAlgorithm.fin_probability_negMulLog_sum_le_log_cardbanditsentropyinformation-theory
Let be a probability vector on a nonempty set of actions. Its Shannon entropy satisfies
Here the convention at is encoded by Real.negMulLog.
Preamble
import Mathlib.Analysis.SpecialFunctions.Log.NegMulLog open scoped BigOperators
Formal statement
theorem BanditAlgorithm.fin_probability_negMulLog_sum_le_log_card {k : ℕ} [NeZero k]
(p : Fin k → ℝ) (hp0 : ∀ a, 0 ≤ p a) (hp1 : ∑ a, p a = 1) :
∑ a, Real.negMulLog (p a) ≤ 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: the diameter of the negative-entropy potential on the k-simplex is log k.