Two-sided Poisson tail for the clause-count concentration proof
ProvedKSATSingleFlip.Connect.poisson_two_sided_tailFor N with Poisson mean r > 0 and x > 0, the probability that |N−r| is at least x is at most 2 exp(−x²/(8(r+x))). This deliberately relaxed bound covers deviations smaller or larger than the mean and is sufficient for the Poisson-count part of Lemma 2.6.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped NNReal set_option autoImplicit false
Formal statement
theorem KSATSingleFlip.Connect.poisson_two_sided_tail (r : ℝ≥0) (hr : 0 < r) (x : ℝ) (hx : 0 < x) :
(poissonMeasure r).real {k : ℕ | x ≤ |(k:ℝ)-(r:ℝ)|} ≤
2*Real.exp (-(x^2)/(8*((r:ℝ)+x))) := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.6, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf