Lemma 28 — Chernoff bound for
ProvedUnionVolEst.lemma_28convex-bodiesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1poisson-samplingrandomized-algorithmsunion-volume-estimation
Let with . Then for every ,
The bound drives the concentration steps of Claims 14, 17 and 20.
Differences from the source:
- generalization: X ∼ Pois(λ) (λ > 0 implicit) → λ ∈ ℝ≥0, including λ = 0; reason: at λ = 0 both sides are trivial; every λ > 0 is covered
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped NNReal
Formal statement
namespace UnionVolEst
/-- Lemma 28 (Chernoff Bound for Poisson Random Variables) (Banerjee–Bal–Basu–Chakraborty–Chanda–Sarkar, *Estimating the Volume of a Union of Convex Bodies*, arXiv:2611.06364 (held version, sha256 15de4f2e…26bd24)), printed p.41, PDF p.43: if
`X ∼ Pois(λ)`, then for every `ε > 0`, `P(|X − λ| > ελ) ≤ 2 exp(−ε²λ/(2(1 + ε)))`.
**Formalization Note** `λ ≥ 0` (`ℝ≥0`); for `λ = 0` the bound is trivial. The probability is
compared in `ℝ≥0∞` via `ENNReal.ofReal`. -/
theorem lemma_28 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(lam : ℝ≥0) (X : Ω → ℕ) (hX : HasLaw X (poissonMeasure lam) P) (ε : ℝ) (hε : 0 < ε) :
P {ω | ε * (lam : ℝ) < |(X ω : ℝ) - lam|} ≤
ENNReal.ofReal (2 * Real.exp (-(ε ^ 2 * lam) / (2 * (1 + ε)))) := by sorry
end UnionVolEst
Source
Banerjee, Bal, Basu, Chakraborty, Chanda, Sarkar, Estimating the Volume of a Union of Convex Bodies, arXiv:2611.06364 (held version, sha256 15de4f2e…26bd24), Lemma 28, p.41 (PDF p.43)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.