BanditAlgorithm.bernoulli_chernoff_tail_bound
Provedchernoffconcentrationprobability
(Chernoff's bound, L&S Lemma 10.3) Let () be independent random variables, Bernoulli distributed with mean (law equality ), and let . Then for ,
and for ,
- Both -ranges are the book's closed intervals, and both conclusions are stated as one conjunction.
- At the junk-valued exponent makes the bound weaker than the book's but still true.
Preamble
import Definitions.Def_bernoulliRelativeEntropy open MeasureTheory ProbabilityTheory Real
Formal statement
theorem BanditAlgorithm.bernoulli_chernoff_tail_bound
{Ω : Type} {mΩ : MeasurableSpace Ω} {P : Measure Ω} [IsProbabilityMeasure P]
{n : ℕ} (hn : 0 < n) {X : Fin n → Ω → ℝ} {μ : ℝ}
(hμ : μ ∈ Set.Icc (0 : ℝ) 1) (h_meas : ∀ i, Measurable (X i))
(h_indep : iIndepFun X P)
(h_law : ∀ i, Measure.map (X i) P =
ENNReal.ofReal μ • Measure.dirac (1 : ℝ) +
ENNReal.ofReal (1 - μ) • Measure.dirac (0 : ℝ)) :
(∀ ε ∈ Set.Icc (0 : ℝ) (1 - μ),
P.real {ω | μ + ε ≤ (∑ t, X t ω) / n} ≤
exp (-(n * bernoulliRelativeEntropy (μ + ε) μ))) ∧
(∀ ε ∈ Set.Icc (0 : ℝ) μ,
P.real {ω | (∑ t, X t ω) / n ≤ μ - ε} ≤
exp (-(n * bernoulliRelativeEntropy (μ - ε) μ))) := by
sorry
Source
L&S Lemma 10.3, p.135 (with Corollary 10.4, p.136)