Lemma 6, p. 15 — Chernoff–Janson tails for a sum of independent Bernoulli variables
ProvedScaleFreeDiam.Main.lemma_6bernoullichernoff-boundconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , where the are independent Bernoulli random variables with , and let . Then for every ,
This is the probabilistic workhorse of §§6–8 of the paper (used in the proofs of Lemmas 7 and 11).
Formalization Note The are measurable real functions on a probability space, mutually independent, and almost surely -valued. When Lean's division by zero gives on the right, which is a true (trivial) bound.
Preamble
import Mathlib
Formal statement
namespace ScaleFreeDiam.Main
open Filter Topology MeasureTheory ProbabilityTheory
open scoped Classical
theorem lemma_6 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(k : ℕ) (X : Fin k → Ω → ℝ) (hXm : ∀ i, Measurable (X i)) (hind : iIndepFun X P)
(hX : ∀ i, ∀ᵐ ω ∂P, X i ω = 0 ∨ X i ω = 1)
(p : Fin k → ℝ) (hp : ∀ i, P.real {ω | X i ω = 1} = p i) (t : ℝ) (ht : 0 ≤ t) :
P.real {ω | (∑ i, p i) + t ≤ ∑ i, X i ω} ≤
Real.exp (-(t ^ 2 / (2 * ((∑ i, p i) + t / 3)))) ∧
P.real {ω | ∑ i, X i ω ≤ (∑ i, p i) - t} ≤
Real.exp (-(t ^ 2 / (2 * (∑ i, p i)))) := by sorry
end ScaleFreeDiam.Main
Source
Bollobás and Riordan, The diameter of a scale-free random graph, Combinatorica 24 (2004), p. 15, Lemma 6 (Janson)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.