Nested candidate-set winner changes have harmonic total probability
ProvedStabilityDichotomies.Bijunctive.iid_exponential_nested_group_change_probabilities_le_harmonicLet be any fixed nested finite candidate sets with fixed labels and independent identically distributed positive-rate exponential scores. Sum, over all steps, the probability that the unique maximum of and a maximum of have different labels. This sum is at most .
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter
Formal statement
theorem StabilityDichotomies.Bijunctive.iid_exponential_nested_group_change_probabilities_le_harmonic
{α κ : Type} [Fintype α] (sets : ℕ → Finset α) (k : ℕ)
(hsub : ∀ i < k, sets (i+1) ⊆ sets i) (label : α → κ) (β : ℝ) (hβ : 0 < β) :
(∑ i ∈ Finset.range k,
(Measure.pi (fun _ : α => expMeasure β)
{δ : α → ℝ | ∃ a ∈ sets i, ∃ b ∈ sets (i+1),
(∀ j ∈ sets i, j ≠ a → δ j < δ a) ∧
(∀ j ∈ sets (i+1), δ j ≤ δ b) ∧ label a ≠ label b}).toReal) ≤
(harmonic (sets 0).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 sensitivity step, equation (8).