Tail bound for the maximum of finitely many exponential shifts
ProvedStabilityDichotomies.Bijunctive.finite_exponential_maximum_tail_boundFor a finite family of independent rate- exponential variables, the probability that at least one exceeds is at most . This is a tail estimate toward bounding the expected maximum in the graph-deletion sensitivity analysis.
Preamble
import Mathlib open scoped Classical BigOperators ENNReal open MeasureTheory ProbabilityTheory Set
Formal statement
theorem StabilityDichotomies.Bijunctive.finite_exponential_maximum_tail_bound {α : Type} [Fintype α]
(β t : ℝ) (hβ : 0 < β) (ht : 0 ≤ t) :
((Measure.pi (fun _ : α => expMeasure β)) {δ : α → ℝ | ∃ i, t < δ i}).toReal ≤
(Fintype.card α : ℝ) * Real.exp (-β*t) := 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.