An exponential tail bound gives a logarithmic expectation bound
ProvedStabilityDichotomies.Bijunctive.integral_of_exponential_tail_boundLet be an integrable nonnegative random variable on a probability space. If for all , with and , then . This supplies the logarithmic expectation estimate used for the maximum shift, once its integrability is established.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter
Formal statement
theorem StabilityDichotomies.Bijunctive.integral_of_exponential_tail_bound {Ω : Type} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] (f : Ω → ℝ)
(hf : Integrable f μ) (hnonneg : ∀ᵐ ω ∂μ, 0 ≤ f ω)
(q β : ℝ) (hq : 1 ≤ q) (hβ : 0 < β)
(htail : ∀ t : ℝ, 0 ≤ t → μ.real {ω | t < f ω} ≤ q * Real.exp (-β*t)) :
(∫ ω, f ω ∂μ) ≤ (Real.log q + 1) / β := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, graph-deletion sensitivity step.