Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 45 min ago
PreprintarXiv licencearXiv

Permutations from ranking independent random variables

  • Luke Turvey
Open at sourcePDFDOICite

Abstract

Let X1,…,Xn be almost surely distinct independent real-valued random variables. Let σ be the random permutation of {1,…,n} such that Xσ(1)<Xσ(2)<⋯< Xσ(n). We show that the set of laws of σ, as the laws of X1,…,Xn vary, has semialgebraic dimension ∑k=2n n choose k(k−1)! as a subset of the (n!−1)-simplex. This establishes a conjecture of Babson, Duchin, Iseli, Poggi-Corradini, Thurston, and Tucker-Foltz who proved that the dimension is upper bounded by the above expression. We prove their conjecture by constructing a family of finitely supported laws for X1,…,Xn that provides the correct dimension. We also give an alternative proof of the upper bound using a theorem of Radford. Furthermore, we show that the Mallows law on permutations cannot arise as a law of σ for n≥ 4, answering a question of Ed Crane.

Related

  1. A Khintchine type inequality for non-independent random variables
    Jingyu Huang, Wenxuan Tao
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  2. A weak invariance principle for triangular arrays of independent random variables in some Besov spaces
    Davide Giraudo, Sadillo Sharipov
    HALPreprintPublisher termsFull textProbabilityStatisticsHALarXiv
  3. Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables
    Haoran Wang
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. The distribution of the ratio of products of independent zero mean normal random variables.
    Robert E Gaunt, Heather L Sutcliffe
    MetrikaPeer-reviewedCC BYFull textStatisticsEurope PMCPMC
  5. Quadratic-size Random Permutations are Universal
    Yu Chen, Yiting Wang
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{turvey2026permutations,
  title = {{Permutations from ranking independent random variables}},
  author = {Luke Turvey},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11895},
  eprint = {2610.11895},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11895},
}
RIS
TY  - UNPB
TI  - Permutations from ranking independent random variables
AU  - Luke Turvey
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.11895
UR  - https://arxiv.org/abs/2610.11895
AB  - Let X_1,…,X_n be almost surely distinct independent real-valued random variables. Let σ be the random permutation of {1,…,n} such that X_σ(1)<X_σ(2)<⋯< X_σ(n). We show that the set of laws of σ, as the laws of X_1,…,X_n vary, has semialgebraic dimension ∑_k=2^n n choose k(k−1)! as a subset of the (n!−1)-simplex. This establishes a conjecture of Babson, Duchin, Iseli, Poggi-Corradini, Thurston, and Tucker-Foltz who proved that the dimension is upper bounded by the above expression. We prove their conjecture by constructing a family of finitely supported laws for X_1,…,X_n that provides the correct dimension. We also give an alternative proof of the upper bound using a theorem of Radford. Furthermore, we show that the Mallows law on permutations cannot arise as a law of σ for n≥ 4, answering a question of Ed Crane.
ER  -