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)
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. Let carry a probability measure, let be a positive natural number, and let . Write for the sample mean, for the real number obtained from the measure of a set, and
with the conventions: division by gives and of any nonpositive number is (so is finite everywhere; e.g. and ).
Assertion (a conjunction of two families of bounds).
Hypotheses.
- ; (closed interval).
- Each is measurable.
- The family is mutually independent under .
- The law of each (the pushforward of ) is exactly the two-point measure on — a Bernoulli() distribution supported on the real points and .
Edge cases.
- is allowed in both parts; for every (including the endpoints, via the conventions), so the bound there is .
- If , the first family ranges over and its exponent uses , the finite conventional value (which is nonpositive), not ; symmetrically, if the second family uses .
- When (resp. ) with interior, the exponent uses (resp. ).
- The events use non-strict inequalities on , and all interval memberships are closed at both ends.
Human review
Confirmed by the mission captain (proposal self-audit).