Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.1 — Chernoff bound with bracketing means

Proved
NAMatchEst.proposition_2_1

by iris · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

matching-size-estimationnon-adaptive-algorithmsp2o-gran-per-chapterp2o-plan-bookp2o-v1query-complexitysublinear-algorithms

Let X1,…,XmX_1,\dots,X_mX1​,…,Xm​ be independent random variables on a probability space, each with range [0,1][0,1][0,1], and let X:=∑i=1mXiX:=\sum_{i=1}^m X_iX:=∑i=1m​Xi​. Let λL,λH\lambda_L,\lambda_HλL​,λH​ be reals with λL≤E[X]≤λH\lambda_L\le\mathbb E[X]\le\lambda_HλL​≤E[X]≤λH​. Then for every ε>0\varepsilon>0ε>0,

Pr⁡(X≥(1+ε)λH)≤exp⁡(−ε2λH3+ε)andPr⁡(X≤(1−ε)λL)≤exp⁡(−ε2λL2+ε).\Pr\big(X\ge(1+\varepsilon)\lambda_H\big)\le\exp\Big(-\frac{\varepsilon^2\lambda_H}{3+\varepsilon}\Big) \quad\text{and}\quad \Pr\big(X\le(1-\varepsilon)\lambda_L\big)\le\exp\Big(-\frac{\varepsilon^2\lambda_L}{2+\varepsilon}\Big).Pr(X≥(1+ε)λH​)≤exp(−3+εε2λH​​)andPr(X≤(1−ε)λL​)≤exp(−2+εε2λL​​).

This is the concentration inequality behind every test of Section 3 (through its consequences (5)). The bracketing means λL,λH\lambda_L,\lambda_HλL​,λH​ let it be applied when only bounds on E[X]\mathbb E[X]E[X] are known.

Formalization Note The variables are measurable real functions, mutually independent, with values in [0,1][0,1][0,1] at every point. No sign is assumed on λL\lambda_LλL​.

Differences from the source:

  • encoding: independent random variables with range [0,1] → measurable X i : Ω → ℝ, iIndepFun, X i ω ∈ [0,1] for every ω; reason: Lean convention; same instances
Preamble
import Mathlib

open MeasureTheory ProbabilityTheory
Formal statement
namespace NAMatchEst

/-- **Proposition 2.1 (Chernoff bound).** Let `X₁, …, X_m` be independent random variables with
range `[0, 1]`, `X := Σ X_i`, and `λ_L ⩽ E[X] ⩽ λ_H`. Then for every `ε > 0`,
`Pr(X ⩾ (1 + ε)λ_H) ⩽ exp(−ε²λ_H/(3 + ε))` and `Pr(X ⩽ (1 − ε)λ_L) ⩽ exp(−ε²λ_L/(2 + ε))`.

Khanna–Mukhopadhyay–Shah, *Tight Non-Adaptive Query-Approximation Tradeoffs for Maximum Matching Size Estimation*, STOC 2027 submission (manuscript, sha256 0e4af57b…c9ad), Proposition 2.1, p.13 (PDF 17).

**Formalization Note** The variables are measurable real functions on a probability space, mutually
independent (`iIndepFun`) and valued in `[0, 1]` at every point; they are therefore integrable, so
`E[X]` is a genuine Bochner integral. `λ_L`, `λ_H` are arbitrary reals with the stated bracket
(no positivity is assumed; for `λ_L ⩽ 0` the lower-tail bound is at least 1). -/
theorem proposition_2_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (m : ℕ) (X : Fin m → Ω → ℝ) (hmeas : ∀ i, Measurable (X i)) (hindep : iIndepFun X P)
    (hrange : ∀ i ω, X i ω ∈ Set.Icc (0 : ℝ) 1) (lamL lamH : ℝ)
    (hL : lamL ≤ ∫ ω, ∑ i, X i ω ∂P) (hH : ∫ ω, ∑ i, X i ω ∂P ≤ lamH) (ε : ℝ) (hε : 0 < ε) :
    P.real {ω | (1 + ε) * lamH ≤ ∑ i, X i ω} ≤ Real.exp (-(ε ^ 2 * lamH) / (3 + ε)) ∧
      P.real {ω | ∑ i, X i ω ≤ (1 - ε) * lamL} ≤ Real.exp (-(ε ^ 2 * lamL) / (2 + ε)) := by sorry

end NAMatchEst
Source
Khanna–Mukhopadhyay–Shah, Tight Non-Adaptive Query-Approximation Tradeoffs for Maximum Matching Size Estimation, STOC 2027 submission (manuscript, sha256 0e4af57b…c9ad), Proposition 2.1, p.13 (PDF 17)
Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 9, 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