Two-sided Bernstein bound for revealed signed sums
ProvedZeroFreeRRG.Hardcore.reveal_two_sided_bernsteinFor independent Bernoulli() vertex revelations and coefficients , the probability that the absolute centered revealed sum is at least is at most for .
Preamble
import Mathlib import Definitions.Def_ZeroFreeRRG_Hardcore_Moments set_option autoImplicit false open Set Filter MeasureTheory AFIsingKS ZeroFreeRRG.Hardcore open scoped Classical BigOperators
Formal statement
theorem ZeroFreeRRG.Hardcore.reveal_two_sided_bernstein (n : ℕ) (s η : ℝ) (z : Fin n → ℝ)
(hs : 0 ≤ s) (hs1 : s ≤ 1) (hη : 0 < η) (hη1 : η ≤ 1)
(hz : ∀ v, |z v| ≤ 1) :
(∑ U : Finset (Fin n), revealProb s U *
(if s*η*n/2 ≤ |(∑ v ∈ U, z v) - s*(∑ v : Fin n, z v)| then 1 else 0)) ≤
2*Real.exp (-(s*η^2/12)*n) := by sorrySource
Auxiliary Bernstein inequality for Chen–Wang–Zhang, Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/1461.pdf, p. 39, proof of Lemma 5.6.