Expected maximum of finitely many exponential shifts
ProvedStabilityDichotomies.Bijunctive.finite_exponential_expected_maximum_boundFor a nonempty finite index set and independent rate- exponential shifts, the maximum with zero is integrable and has expectation at most . This provides the logarithmic expected shift bound needed by the graph-deletion sensitivity analysis.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter
Formal statement
theorem StabilityDichotomies.Bijunctive.finite_exponential_expected_maximum_bound {α : Type} [Fintype α] [Nonempty α]
(β : ℝ) (hβ : 0 < β) :
let μ := Measure.pi (fun _ : α => expMeasure β)
let M := fun δ : α → ℝ => max 0 (Finset.univ.sup' Finset.univ_nonempty δ)
Integrable M μ ∧ (∫ δ, M δ ∂μ) ≤ (Real.log (Fintype.card α) + 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.