Proposition 3.4 — Full bounded-variable multiplicative Chernoff bound
ProvedMaxCutMatrix2027.Upper.multiplicative_chernoffgraph-property-testingmaximum-cutp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be independent real random variables on an arbitrary probability space, with almost surely. Put and . For every real ,
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.