Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.4 — Chernoff upper and lower tails for independent [0,1]-valued variables

Proved
DynColorWC.Main.lemma_3_4

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

almost-clique-decompositiondynamic-graph-algorithmsgraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let X1,…,Xn∈[0,1]X_1,\dots,X_n\in[0,1]X1​,…,Xn​∈[0,1] be mutually independent random variables and X=∑iXiX=\sum_iX_iX=∑i​Xi​. Then for all δ>0\delta>0δ>0,

Pr⁡[X≥(1+δ)E[X]]≤exp⁡(−δ2E[X]2(1+δ)),\Pr[X\ge(1+\delta)\mathbb E[X]]\le\exp\Big(-\frac{\delta^2\mathbb E[X]}{2(1+\delta)}\Big),Pr[X≥(1+δ)E[X]]≤exp(−2(1+δ)δ2E[X]​),

and for all δ∈[0,1]\delta\in[0,1]δ∈[0,1], Pr⁡[X≤(1−δ)E[X]]≤exp⁡(−δ2E[X]/2)\Pr[X\le(1-\delta)\mathbb E[X]]\le\exp(-\delta^2\mathbb E[X]/2)Pr[X≤(1−δ)E[X]]≤exp(−δ2E[X]/2).

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
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me