Theorem 4 — Chernoff:
ProvedPercCubeCycles.theorem_4concentrationp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For a binomial random variable and any ,
This is the Chernoff bound the paper uses for binomial counts.
Differences from the source:
- encoding: binomial, →
ProbabilityTheory.binomial n p, with ; reason: the mean is written out - encoding: the bound at → and the bound is , since in Lean; reason: the printed bound is undefined there, and the statement is trivially true
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace PercCubeCycles
/-- Theorem 4, p.7 (Chernoff bound), Anastos, *Linear-length cycles in the supercritical percolated hypercube*, STOC 2027 submission (sha256 14e6f0ee…). For a binomial random variable `X` and any
`t ∈ [0, E[X]]`, `Pr[|X − E X| ≥ t] ≤ 2 exp(−t² / (3 E[X]))`.
**Formalization Note.** `X ∼ Bin(n, p)` is `ProbabilityTheory.binomial n p`, with `E[X] = np`. At `np = 0`
the range forces `t = 0`, and the bound is `2` (`0 / 0 = 0` in Lean), which is true. -/
theorem theorem_4 (n : ℕ) (p : unitInterval) (t : ℝ) (ht₀ : 0 ≤ t) (ht : t ≤ n * (p : ℝ)) :
ProbabilityTheory.binomial n p {x : ℕ | t ≤ |(x : ℝ) - n * (p : ℝ)|}
≤ ENNReal.ofReal (2 * Real.exp (-t ^ 2 / (3 * (n * (p : ℝ))))) := by sorry
end PercCubeCycles
Source
Anastos, Linear-length cycles in the supercritical percolated hypercube, STOC 2027 submission (sha256 14e6f0eeea86205c661b9ec5b7259d5e903f4bcfacef3946a425ea6e60e837ae), Theorem 4, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.