The complete ordering of an iid atomless sample is uniform
ProvedStabilityDichotomies.Bijunctive.iid_continuous_order_uniformFor independent identically distributed real random variables with no pairwise ties, every strict ordering of the coordinates occurs with probability . This is the joint random priority and cutoff ordering used in the proof of Theorem 4.9.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function
Formal statement
theorem StabilityDichotomies.Bijunctive.iid_continuous_order_uniform (n : ℕ) (μ₀ : Measure ℝ) [IsProbabilityMeasure μ₀]
(htie : ∀ a b : Fin n, a ≠ b →
Measure.pi (fun _ : Fin n => μ₀) {x | x a = x b} = 0)
(e : Equiv.Perm (Fin n)) :
(Measure.pi (fun _ : Fin n => μ₀)
{x | ∀ i, (Finset.univ.filter (fun j : Fin n => x j < x i)).card = (e i).val}).toReal = 1 / n.factorial := 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.