Removing a candidate group changes the winner label with probability at most its fraction
ProvedStabilityDichotomies.Bijunctive.iid_exponential_group_removal_change_boundFor i.i.d. rate- exponential scores on a finite candidate set , remove a subset and compare arbitrary fixed labels of the original unique maximum and a maximum remaining in . The probability that their labels differ is at most . The event explicitly requires the original maximum to be unique.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter
Formal statement
theorem StabilityDichotomies.Bijunctive.iid_exponential_group_removal_change_bound {α κ : Type} [Fintype α]
(T S : Finset α) (hsub : S ⊆ T) (label : α → κ) (β : ℝ) (hβ : 0 < β) :
(Measure.pi (fun _ : α => expMeasure β)
{δ : α → ℝ | ∃ a ∈ T, ∃ b ∈ S,
(∀ j ∈ T, j ≠ a → δ j < δ a) ∧
(∀ j ∈ S, δ j ≤ δ b) ∧ label a ≠ label b}).toReal ≤
((T \ S).card : ℝ) / T.card := 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, feasibility-root record analysis.