A specified index is maximal on a subset with probability 1/|S|
ProvedStabilityDichotomies.Bijunctive.iid_exponential_subset_maximum_uniformFor independent rate- exponential values indexed by a finite set, and any nonempty subset containing , the probability that is the unique maximum over is exactly . Coordinates outside are unrestricted.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function
Formal statement
theorem StabilityDichotomies.Bijunctive.iid_exponential_subset_maximum_uniform {α : Type} [Fintype α]
(S : Finset α) (i : α) (hi : i ∈ S) (β : ℝ) (hβ : 0 < β) :
(Measure.pi (fun _ : α => expMeasure β)
{δ : α → ℝ | ∀ j ∈ S, j ≠ i → δ j < δ i}).toReal = 1 / S.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.