1
$\begingroup$

It seems quite "obvious" that if you sort a $n$-tuple of i.i.d. variables (assuming they have an order and ties do not exist - which is true with probability $1$ for, say, $U(0, 1)$) that the resulting permutation is a uniformly random one - after all what would be the source of any bias? But obvious does not mean proven, and I've struggled for a bit to come up with a proof. I think I have done so now, but I feel like it is overly complicated, a bit informal, and most importantly, "backwards". Is there a simpler proof?


Let $r$ be a tuple of $n$ i.i.d. random variables (with an order and no equal elements with probability $1$). Let $\sigma$ be a permutation chosen at uniformly at random from the $n!$ possible permutations on $n$ elements, independent from $r$.

Note that $\sigma(r)$ samples from the same distribution as $r$, since any blind (independent of $r$) reordering of i.i.d. variables is indistinguishable from the original. We can thus see that $s = \sigma(\mathrm{sort}(r))$ also samples from the same distribution as $r$, since $\sigma$ is a random permutation which destroys all information about order prior to the permutation, making the sort irrelevant and the two indistinguishable.

By sorting $s$ we get $\sigma^{-1}$, the inverse of a randomly chosen permutation, assuming there are no duplicate elements. But since there is a one-to-one mapping between $n$-permutations and their inverses, and $\sigma$ was chosen uniformly at random, $\sigma^{-1}$ samples from the same distribution as $\sigma$.

Since $s$ is distributed like $r$, and $\sigma^{-1}$ is distributed like $\sigma$ we can thus conclude that by sampling $r$ and sorting it we can sample from a $n$-permutation uniformly at random.

$\endgroup$
5
  • $\begingroup$ This is the kind of thing where you have to be precise about the meaning of the terms to make the intuition provable directly. Specifically, not all sequences do not give a unique permutation, if values are equal. You need the probability that two values are equal is $0.$ That means your distribution has to be continuous, or you need a statement that "given that the $X_i$ are distinct, then..." $\endgroup$ Jul 13, 2022 at 17:14
  • $\begingroup$ @ThomasAndrews I am assuming the distribution is continuous, essentially. I think saying "given that the $X_i$ are distinct" is highly problematic because that directly violates the i.i.d. assumption. I don't see a better solution than to say that with probability $1$ the elements are distinct. $\endgroup$
    – orlp
    Jul 13, 2022 at 17:19
  • $\begingroup$ Not really, it is a conditional probably question. You are trying to prove, for any permutation $\sigma,$ that $P\left(Y=\sigma\mid X_1,X_2,\dots,X_n\text{ distinct}\right)=1/n!.$ $Y$ is something undefined - a non-permutation - if the $X_i$ are not distinct. $\endgroup$ Jul 13, 2022 at 17:21
  • $\begingroup$ In any event, for continuous probabilities, this can be thought of as a question about $[0,1]^n$ partitioned into $n!$ subsets, each sorted by each permutation $\sigma,$ the the measure-zero of points where the coordinates are not distinct. Then you can show the parts of the partition are all congruent by finding simple explicit congruences. $\endgroup$ Jul 13, 2022 at 17:29
  • $\begingroup$ If $f_{X}:\mathbb R\to [0,1]$ is the continuous CDF, then the continuous inverse $Y_i=f_X(X_i)$ are iid uniform in $[0,1],$ with the same sorting properties - the sorting permutation for $Y_i$ is the same as the sorting permutation of $X_i.$ $\endgroup$ Jul 13, 2022 at 18:10

1 Answer 1

1
$\begingroup$

First you need to ensure that ties are not possible. If $P(X_1 = x) = 0$ for all $x$, then this is satisfied.

Thus the order of $X = (X_1, \dots, X_n)$ defines a well defined random permutation $s(X)$ meaning that $X_{s(X)(1)} < \dots < X_{s(X)(n)}$. Now we want to show that $s(X)$ has the uniform distribution on $S_n$, i.e. that for every $\sigma \in S_n$, $P(s(X) = \sigma) = \frac{1}{n!}$. To show this, it suffices to show that $P(s(X) = \sigma) = P(s(X) = id)$ for all $\sigma\in S_n$. Note that $\{s(X) = \sigma\} = \{s(X_{\sigma(1)}, \dots, X_{\sigma(n)}) = id\}$. So it suffices to show that $(X_1, \dots, X_n)$ and $(X_{\sigma(1)}, \dots, X_{\sigma(n)})$ have the same distribution. But this is true by the $\pi-\lambda$ theorem since by the i.i.d assumption, their joint laws agree on sets of the form $A_1 \times \dots \times A_n$ with $A_1, \dots, A_n \subset \mathbb{R}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .