Exponential short-interval hazard bound
ProvedStabilityDichotomies.Bijunctive.exponential_interval_hazard_boundexponential-distributionprobability
For X distributed exponentially with rate β > 0, any real threshold a and t ≥ 0, P(a < X ≤ a+t) is at most (1−exp(−βt))P(X>a), and this is at most βt·P(X>a). The bound remains valid for thresholds below zero and provides the conditional one-coordinate estimate for the shifted-exponential gap lemma.
Preamble
import Mathlib noncomputable section open MeasureTheory ProbabilityTheory Set
Formal statement
theorem StabilityDichotomies.Bijunctive.exponential_interval_hazard_bound (β a t : ℝ) (hβ : 0 < β) (ht : 0 ≤ t) :
(expMeasure β).real (Ioc a (a+t)) ≤
(1 - Real.exp (-β * t)) * (expMeasure β).real (Ioi a) ∧
(1 - Real.exp (-β * t)) * (expMeasure β).real (Ioi a) ≤
(β * t) * (expMeasure β).real (Ioi a) := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, Lemma 4.5, p. 18, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf