Theorem 9.2 (Chernoff bounds): additive and multiplicative tail bounds for m independent Bernoulli trials
ProvedComputationalLearning.chernoff_boundschernoff-boundsconcentrationprobability
Theorem 9.2. Let be a sequence of independent Bernoulli trials, each with probability of success . Let , so . Then for : (additive form) and ; (multiplicative form) and .
Formally, on the product law of Bernoulli() trials, , the four bounds with non-strict inequalities in the events (stronger than the printed strict ones).
Preamble
import Definitions.Def_ComputationalLearning_Boosting open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning
/-- **Theorem 9.2 (Chernoff bounds)** (p. 190). Let `X₁, …, Xₘ` be independent Bernoulli trials
with success probability `p` and `S = X₁ + ⋯ + Xₘ`, so `E[S] = pm`. Then for `0 < γ ≤ 1`:
(additive form) `Pr[S ≥ (p + γ)m] ≤ e^{−2mγ²}` and `Pr[S ≤ (p − γ)m] ≤ e^{−2mγ²}`;
(multiplicative form) `Pr[S ≥ (1 + γ)pm] ≤ e^{−mpγ²/3}` and `Pr[S ≤ (1 − γ)pm] ≤ e^{−mpγ²/2}`. -/
theorem chernoff_bounds {p : ℝ} (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (m : ℕ) {γ : ℝ} (hγ : 0 < γ)
(hγ1 : γ ≤ 1) :
trialsLaw p m {ω | (p + γ) * m ≤ successes ω} ≤ ENNReal.ofReal (Real.exp (-(2 * m * γ ^ 2))) ∧
trialsLaw p m {ω | (successes ω : ℝ) ≤ (p - γ) * m} ≤
ENNReal.ofReal (Real.exp (-(2 * m * γ ^ 2))) ∧
trialsLaw p m {ω | (1 + γ) * p * m ≤ successes ω} ≤
ENNReal.ofReal (Real.exp (-(m * p * γ ^ 2 / 3))) ∧
trialsLaw p m {ω | (successes ω : ℝ) ≤ (1 - γ) * p * m} ≤
ENNReal.ofReal (Real.exp (-(m * p * γ ^ 2 / 2))) := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, Chapter 9, §9.3 p. 190, Theorem 9.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.