Lemma 3.4 — Chernoff upper and lower tails for independent [0,1]-valued variables
ProvedDynColorWC.Main.lemma_3_4almost-clique-decompositiondynamic-graph-algorithmsgraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be mutually independent random variables and . Then for all ,
and for all , .
Differences from the source:
- encoding: mutually independent X_1, …, X_n ∈ [0, 1] with E[X] → measurable X : Fin n → Ω → ℝ, iIndepFun under a probability measure, 0 ≤ X_i ω ≤ 1 at every ω; E[X] is the Bochner integral of Σ X_i and P is μ.real; reason: bounded measurable variables are integrable, so E[X] is genuine
Preamble
import Mathlib
Formal statement
namespace DynColorWC.Main
open MeasureTheory ProbabilityTheory
/-- **Lemma 3.4** (Chernoff bound; Flin and Ghaffari (2026), STOC 2027 submission,
sha256 93ebb2ff…3154300e3, p. 14 (PDF 16)). Let `X_1, …, X_n ∈ [0, 1]` be mutually independent random
variables and `X = Σ_i X_i`. Then for all `δ > 0`,
`P[X ≥ (1 + δ) E[X]] ≤ exp(−δ² E[X] / (2(1 + δ)))`, and for all `δ ∈ [0, 1]`,
`P[X ≤ (1 − δ) E[X]] ≤ exp(−δ² E[X] / 2)`. -/
theorem lemma_3_4 {Ω : Type} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (n : ℕ)
(X : Fin n → Ω → ℝ) (hmeas : ∀ i, Measurable (X i)) (hind : iIndepFun X μ)
(hrange : ∀ i ω, 0 ≤ X i ω ∧ X i ω ≤ 1) :
(∀ δ : ℝ, 0 < δ →
μ.real {ω | (1 + δ) * (∫ ω', ∑ i, X i ω' ∂μ) ≤ ∑ i, X i ω} ≤
Real.exp (-(δ ^ 2 * (∫ ω', ∑ i, X i ω' ∂μ)) / (2 * (1 + δ)))) ∧
(∀ δ : ℝ, 0 ≤ δ → δ ≤ 1 →
μ.real {ω | ∑ i, X i ω ≤ (1 - δ) * (∫ ω', ∑ i, X i ω' ∂μ)} ≤
Real.exp (-(δ ^ 2 * (∫ ω', ∑ i, X i ω' ∂μ)) / 2)) := by sorry
end DynColorWC.Main
Source
Flin and Ghaffari (2026), Dynamic (Δ+1)-Coloring with Polylogarithmic Worst-Case Update Time, STOC 2027 submission, supplied PDF sha256 93ebb2ffd4839b5e525b4550a6569cf5234550ee4a44351aedab3ea3154300e3, Lemma 3.4, p. 14 (PDF 16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.