Eq. (18) — Chernoff–Hoeffding bound for the binomial distribution
ProvedBayesProphet.MultiSec.binomial_chernoff_hoeffdingbinomialconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , , , and , so that . Then
The paper quotes this from Dubhashi–Panconesi [22, Theorem 1.1] and uses it with to bound the disagreement probabilities of the Fluid Bayes Selector.
Formalization Note The probabilities are written as sums of the binomial mass function over . The hypothesis is implicit in the paper (the bound is false for ).
Preamble
import Mathlib
Formal statement
namespace BayesProphet.MultiSec
theorem binomial_chernoff_hoeffding (t : ℕ) (α ε : ℝ) (hα₀ : 0 ≤ α) (hα₁ : α ≤ 1)
(hε : 0 ≤ ε) :
∑ k ∈ (Finset.range (t + 1)).filter (fun k : ℕ => (k : ℝ) - t * α ≤ -(t * ε)),
(t.choose k : ℝ) * α ^ k * (1 - α) ^ (t - k) ≤ Real.exp (-2 * ε ^ 2 * t) ∧
∑ k ∈ (Finset.range (t + 1)).filter (fun k : ℕ => t * ε ≤ (k : ℝ) - t * α),
(t.choose k : ℝ) * α ^ k * (1 - α) ^ (t - k) ≤ Real.exp (-2 * ε ^ 2 * t) := by sorry
end BayesProphet.MultiSec
Source
Vera & Banerjee, The Bayesian Prophet: A Low-Regret Framework for Online Decision Making, SSRN 3158062 (doi:10.2139/ssrn.3158062), p. 37, Eq. (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.