A designated coordinate in an iid atomless sample has uniform rank
ProvedStabilityDichotomies.Bijunctive.iid_continuous_rank_uniformLet be independent, identically distributed real random variables, and suppose distinct coordinates tie with probability zero. For every coordinate and every ,
This supplies the uniform-cutoff-rank component of the random ordering argument in Theorem 4.9.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function
Formal statement
theorem StabilityDichotomies.Bijunctive.iid_continuous_rank_uniform (n : ℕ) (μ₀ : Measure ℝ) [IsProbabilityMeasure μ₀]
(htie : ∀ a b : Fin n, a ≠ b →
Measure.pi (fun _ : Fin n => μ₀) {x | x a = x b} = 0)
(i k : Fin n) :
(Measure.pi (fun _ : Fin n => μ₀) {x | (Finset.univ.filter (fun j : Fin n => x j < x i)).card = k.val}).toReal = 1 / n := 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, random cutoff-rank argument.