Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.4 — Full bounded-variable multiplicative Chernoff bound

Proved
MaxCutMatrix2027.Upper.multiplicative_chernoff

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

graph-property-testingmaximum-cutp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let X1,…,XmX_1,\ldots,X_mX1​,…,Xm​ be independent real random variables on an arbitrary probability space, with 0≤Xi≤10\le X_i\le10≤Xi​≤1 almost surely. Put S=∑iXiS=\sum_i X_iS=∑i​Xi​ and μ=ES>0\mu=\mathbb E S>0μ=ES>0. For every real δ>0\delta>0δ>0,

Pr⁡{S≥(1+δ)μ}≤exp⁡(−δ2μ2+δ).\Pr\{S\ge(1+\delta)\mu\}\le\exp\left(-\frac{\delta^2\mu}{2+\delta}\right).Pr{S≥(1+δ)μ}≤exp(−2+δδ2μ​).

The variables need not be Bernoulli, identically distributed or finite-valued, and there is no upper restriction on the deviation parameter. Measurability is the standard meaning of random variable. The almost-sure bounds imply integrability on the probability space, so no default integral value is used. This gives the sample-overflow tail bound without narrowing the proposition to that application.

Differences from the source:

  • encoding: independent random variables and their probability → measurable functions on an arbitrary probability space, iIndepFun, and the real value of the finite event measure; reason: these are the standard measurable-random-variable convention and the identical probability law
Preamble
import Mathlib
set_option autoImplicit false
open MeasureTheory ProbabilityTheory
open scoped BigOperators
Formal statement
namespace MaxCutMatrix2027.Upper

/-- Proposition 3.4, p.16. Arbitrary independent bounded real random variables;
all positive deviations, exact denominator 2+δ. -/
theorem multiplicative_chernoff {Ω : Type*} [MeasurableSpace Ω]
    (μ : Measure Ω) [IsProbabilityMeasure μ] (m : ℕ) (X : Fin m → Ω → ℝ)
    (hX : ∀ i, Measurable (X i)) (hind : iIndepFun X μ)
    (hb : ∀ i, ∀ᵐ ω ∂μ, X i ω ∈ Set.Icc (0 : ℝ) 1)
    (hmean : 0 < ∫ ω, ∑ i, X i ω ∂μ) (δ : ℝ) (hδ : 0 < δ) :
    μ.real {ω | (1 + δ) * (∫ z, ∑ i, X i z ∂μ) ≤ ∑ i, X i ω} ≤
      Real.exp (-(δ ^ 2 * (∫ z, ∑ i, X i z ∂μ)) / (2 + δ)) := by sorry

end MaxCutMatrix2027.Upper
Source
Songhua He, STOC 2027 submission #351 (October 2026), Proposition 3.4, p.16 (PDF p.16); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/351.pdf; PDF SHA-256 b38cd84079663d9e2eb7375d7bf1572d5dc7c2157cfaf90e175fd371a9503631
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · 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