Mean absolute deviation of a Poisson clause count
ProvedKSATSingleFlip.Connect.poisson_mean_absolute_deviationIf N has a Poisson distribution with mean r ≥ 0, then its mean absolute deviation from r is at most √r. This is the mean-fluctuation estimate used in the proof of 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_mean_absolute_deviation (r : ℝ≥0) :
(∫ k : ℕ, |(k:ℝ) - (r:ℝ)| ∂(poissonMeasure r)) ≤ Real.sqrt (r:ℝ) := 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