Theorem A.1 (Chernoff bound) —
ProvedDDNNFNeg.theorem_A_1boolean-functionscircuit-complexityknowledge-compilationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be independent random variables taking values in , let and . Then for any ,
This is the tail bound applied to the independent coins in the proof of Lemma 5.6.
Formalization Note The random variables are measurable real functions on a probability space, mutually independent, with values in at every point; the success probabilities are arbitrary. The paper's is written .
Differences from the source:
- encoding: independent random variables X₁, …, X_n with values in {0,1} → measurable functions X i : Ω → ℝ on a probability space, iIndepFun, X i ω ∈ {0,1}; n renamed m; reason: Lean's representation of random variables; same instances
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace DDNNFNeg
/-- **Theorem A.1** (Chernoff bound) (Arenas–Broadrick–Liew–Van den Broeck, *d-DNNF is Not Polynomially Closed Under Negation*, STOC 2027 submission manuscript (sha256 64e42127…fbb68), p.27): let `X₁, …, X_m` be independent random
variables taking values in `{0, 1}`, `X = ∑ᵢ Xᵢ` and `μ = E[X]`. Then for any `δ ∈ (0, 1)`,
`P[X ≤ (1 − δ)μ] ≤ e^{−δ²μ/2}`.
**Formalization Note** The random variables are measurable real functions on a probability
space, mutually independent (`iIndepFun`), with values in `{0, 1}` at every point; their
success probabilities are arbitrary. The paper's `n` is written `m`. -/
theorem theorem_A_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(m : ℕ) (X : Fin m → Ω → ℝ) (hXm : ∀ i, Measurable (X i)) (hind : iIndepFun X P)
(h01 : ∀ i ω, X i ω = 0 ∨ X i ω = 1) (δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1) :
P.real {ω | ∑ i, X i ω ≤ (1 - δ) * ∫ ω', ∑ i, X i ω' ∂P} ≤
Real.exp (-(δ ^ 2 * ∫ ω', ∑ i, X i ω' ∂P) / 2) := by sorry
end DDNNFNeg
Source
Arenas–Broadrick–Liew–Van den Broeck, d-DNNF is Not Polynomially Closed Under Negation, STOC 2027 submission manuscript (sha256 64e4212767c37c44…fbb68), Theorem A.1, p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.