Lemma 18, p. 28 — the maximum X of n i.i.d. standard exponentials satisfies E[e^{tX}] ≤ n^t/(1 − t) for t ∈ (0, 1)
ProvedLimitedSwitching.HighProb.lemma_18exponential-distributionmoment-generating-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let and let , where are i.i.d. standard exponential random variables. Then for every ,
This moment-generating-function bound is the input of the Chernoff argument for Lemma 9.
Formalization Note The expectation is a lower Lebesgue integral in , so it is the true expectation and integrability is not presupposed. At the bound holds with equality.
Preamble
import Mathlib import Definitions.Def_LimitedSwitching_HighProb_Setting open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace LimitedSwitching.HighProb
theorem lemma_18 {n : ℕ} [NeZero n] (t : ℝ) (ht0 : 0 < t) (ht1 : t < 1) :
∫⁻ R, ENNReal.ofReal (Real.exp (t * Finset.univ.sup' Finset.univ_nonempty R)) ∂(expLaw n)
≤ ENNReal.ofReal ((n : ℝ) ^ t / (1 - t)) := by sorry
end LimitedSwitching.HighProb
Source
Altschuler & Talwar, Online learning over a finite action set with limited switching, arXiv:1803.01548v2, p. 28, Appendix D, Lemma 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.