Exponential hazard bound above an independent random threshold
ProvedStabilityDichotomies.Bijunctive.independent_random_threshold_hazardexponential-distributionprobability
Let X be exponential of rate β > 0 and independent of a measurable real threshold a(Y), where Y has any s-finite measure. For every t ≥ 0, the joint measure of a(Y)<X≤a(Y)+t is at most (1−exp(−βt)) times the joint measure of X>a(Y). This is the product-measure conditioning step underlying the source shifted-exponential top-gap lemma.
Preamble
import Mathlib noncomputable section open scoped Classical ENNReal open MeasureTheory ProbabilityTheory Set
Formal statement
theorem StabilityDichotomies.Bijunctive.independent_random_threshold_hazard {Ω : Type} [MeasurableSpace Ω]
(ν : Measure Ω) [SFinite ν] (a : Ω → ℝ) (ha : Measurable a)
(β t : ℝ) (hβ : 0 < β) (ht : 0 ≤ t) :
((expMeasure β).prod ν {z : ℝ × Ω | a z.2 < z.1 ∧ z.1 ≤ a z.2 + t}) ≤
ENNReal.ofReal (1 - Real.exp (-β*t)) *
((expMeasure β).prod ν {z : ℝ × Ω | a z.2 < z.1}) := 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