Close maxima on disjoint subsets of independent shifted exponentials
ProvedStabilityDichotomies.Bijunctive.disjoint_subsets_maxima_close_probabilityFor disjoint nonempty subsets of a finite index set, let each be an independent rate- exponential variable minus a fixed real offset. For , the probability that the maxima on and differ by at most is at most . Variables indexed outside do not affect the event.
Preamble
import Mathlib open scoped Classical ENNReal open MeasureTheory ProbabilityTheory Set
Formal statement
theorem StabilityDichotomies.Bijunctive.disjoint_subsets_maxima_close_probability {α : Type} [Fintype α] (s t : Finset α)
(hs : s.Nonempty) (ht : t.Nonempty) (hdis : Disjoint s t)
(β r : ℝ) (hβ : 0 < β) (hr : 0 ≤ r) (d : α → ℝ) :
((Measure.pi (fun _ : α => expMeasure β)) {δ : α → ℝ | ∃ a ∈ s, ∃ b ∈ t, (∀ k ∈ s, δ k - d k ≤ δ a - d a) ∧ (∀ k ∈ t, δ k - d k ≤ δ b - d b) ∧ (δ a - d a) - (δ b - d b) ≤ r ∧ (δ b - d b) - (δ a - d a) ≤ r}).toReal ≤
1 - Real.exp (-β*r) := 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, approximation paragraph.