Uniformity of Rank Permutations

Why Rank Permutations Are Uniform

For an iid sample, the observations have identical distributions and are interchangeable: relabeling the observations does not change their joint distribution. If the common distribution has no atoms, ties occur with probability zero, so each observation receives a distinct rank. Together, these facts imply a precise symmetry: every possible assignment of ranks to the observation labels is equally likely.

This result is useful whenever a question depends only on the relative ordering of observations. Instead of working with the sample values or their particular distribution, one can count rank permutations. The calculation still requires care: the rank variables are not independent, and the no-ties condition matters.

Definition: Let $X_1,\ldots,X_n$ be an iid sample from an atomless distribution, meaning $P(X_i=x)=0$ for every real $x$. The ascending rank of observation $i$ is $$ R_i=1+\sum_{\substack{j=1\\j\ne i}}^n \mathbf{1}\{X_j<X_i\}. $$ Thus $R_i=1$ for the smallest observation and $R_i=n$ for the largest. With probability one, the vector $(R_1,\ldots,R_n)$ is a permutation of $1,\ldots,n$.

The atomless assumption rules out ties. For any distinct $i,j$, independence gives $P(X_i=X_j)=\int P(X_j=x)\,dF(x)=0$. There are only finitely many pairs, so the probability of any tie in the sample is also zero. The result below needs no density: an atomless distribution may be continuous without having a density.

The Uniformity Theorem

Theorem: If $X_1,\ldots,X_n$ are iid from an atomless distribution, then for every permutation $r=(r_1,\ldots,r_n)$ of $1,\ldots,n$, $$ P\bigl((R_1,\ldots,R_n)=r\bigr)=\frac{1}{n!}. $$

To prove the theorem, describe each possible ordering by the labels of the observations from smallest to largest. For a permutation $\pi=(\pi_1,\ldots,\pi_n)$, define $$ E_\pi=\{X_{\pi_1}<X_{\pi_2}<\cdots<X_{\pi_n}\}. $$ Except on the probability-zero event of a tie, exactly one such ordering occurs. These $n!$ events are disjoint and cover the sample space up to that null event.

Their probabilities are equal. Indeed, for any two label orderings $\pi$ and $\tau$, relabel the coordinates so that the observation in position $k$ of $\pi$ is sent to the observation in position $k$ of $\tau$, for every $k$. Under this coordinate relabeling, $E_\pi$ is mapped to $E_\tau$. Because the sample is iid, its joint distribution is unchanged by any coordinate permutation; consequently $P(E_\pi)=P(E_\tau)$. If their common probability is $p$, disjointness and coverage give $n!p=1$, hence $p=1/n!$.

Finally, the event $(R_1,\ldots,R_n)=r$ specifies exactly one ordering: the index with rank 1 comes first, the index with rank 2 comes second, and so on. Thus its probability is the probability of one of the events $E_\pi$, which is $1/n!$. This proves the theorem. $\square$

Counting consequence: Let $A$ be any set of permutations of $1,\ldots,n$. Under the theorem's assumptions, $$ P\bigl((R_1,\ldots,R_n)\in A\bigr)=\frac{|A|}{n!}, $$ where $|A|$ is the number of permutations in $A$. The events for distinct rank vectors are disjoint, and each has probability $1/n!$, so adding their probabilities proves the formula.

Worked Rank-Pattern Calculations

Worked Example: One Exact Rank Assignment

Suppose $n=4$, and find the probability that observation 1 is second smallest, observation 2 is largest, observation 3 is smallest, and observation 4 is third smallest.

The specified rank vector is $(2,4,1,3)$, which is one of the $4!=24$ possible rank permutations. Therefore $$ P\bigl((R_1,R_2,R_3,R_4)=(2,4,1,3)\bigr)=\frac{1}{4!}=\frac{1}{24}. $$ Equivalently, the ordering is $X_3<X_1<X_4<X_2$, one of the 24 possible strict orderings. The calculation does not depend on the form of the common atomless distribution.

Worked Example: The First Two Observations Are the Two Smallest

For $n=5$, find the probability that observations 1 and 2 occupy ranks 1 and 2 in either order.

The first two ranks can be assigned to observations 1 and 2 in $2!$ ways. The remaining ranks, 3, 4, and 5, can be assigned to observations 3, 4, and 5 in $3!$ ways. The number of compatible rank permutations is therefore $2!3!=12$, out of $5!=120$. Hence $$ P\bigl(\{R_1,R_2\}=\{1,2\}\bigr)=\frac{2!3!}{5!}=\frac{12}{120}=\frac{1}{10}. $$ The set notation allows either $R_1=1,R_2=2$ or $R_1=2,R_2=1$; counting only one of those assignments would incorrectly halve the probability.

Worked Example: Two Simultaneous Ordering Constraints

For $n=4$, find $P(R_1<R_2\text{ and }R_3<R_4)$.

Choose the two ranks that will be assigned to observations 1 and 2. There are $\binom{4}{2}=6$ choices. Once those two ranks are chosen, the condition $R_1<R_2$ determines which one goes to observation 1 and which goes to observation 2. The other two ranks go to observations 3 and 4, with $R_3<R_4$ determining their assignment. Thus each choice gives exactly one compatible permutation, for a total of 6. It follows that $$ P(R_1<R_2,\ R_3<R_4)=\frac{6}{4!}=\frac{6}{24}=\frac{1}{4}. $$ As a check, each of the two pairwise order conditions has probability $1/2$, but multiplying those probabilities would require independence. The counting argument, not an assumption of independence, justifies the answer here.

Relative Orders Among Selected Observations

A useful general count concerns only a selected group of observations. For any $k$ distinct labels, where $1\le k\le n$, each of their $k!$ possible relative orders has probability $1/k!$. To verify this, fix one proposed relative order. Choose the $k$ ranks occupied by the selected observations in $\binom{n}{k}$ ways. For each choice, assigning those ranks in the fixed relative order is uniquely determined. The other $n-k$ labels can fill the remaining ranks in $(n-k)!$ ways. Therefore the number of permutations with the proposed relative order is $$ \binom{n}{k}(n-k)!=\frac{n!}{k!}. $$ Dividing by the total of $n!$ permutations gives probability $1/k!$. Since the count is the same for every proposed relative order, all $k!$ possibilities have equal probability.

Worked Example: A Relative Order Among Three Observations

Let $n=6$. Find the probability that $X_2<X_5<X_6$, without restrictions on the other three observations.

Among observations 2, 5, and 6, there are $3!=6$ equally likely relative orders. The displayed ordering is just one of them, so $$ P(X_2<X_5<X_6)=\frac{1}{3!}=\frac{1}{6}. $$ For a direct count, choose the three ranks for these observations in $\binom{6}{3}=20$ ways. Their ranks must be assigned to observations 2, 5, and 6 in the stated order, while the other three observations can be assigned the remaining ranks in $3!=6$ ways. Thus $20\cdot6=120$ of the $6!=720$ permutations qualify, and $120/720=1/6$, as before.

Common Pitfalls and Scope

Assuming rank coordinates are independent. Uniformity applies to the whole rank vector as a permutation, not to independent choices of its coordinates. For example, when $n=3$, each of $R_1$ and $R_2$ has marginal probability $1/3$ of equaling 1 and probability $1/3$ of equaling 2. But $P(R_1=1,R_2=2)=1/6$, not the product $1/9$: the product would be valid only under independence. In fact, rank coordinates must collectively use each rank exactly once.
Counting only one version of an “either order” event. If two labelled observations may occupy two ranks in either order, count both assignments, as in the event $\{R_1,R_2\}=\{1,2\}$.
Ignoring ties. The theorem concerns strict ranks in an iid sample with no ties almost surely. With a distribution that has atoms, strict rank permutations need not cover all outcomes. A rule for handling ties would define a different rank problem.
Using the result for non-identically distributed observations. Independence alone does not make the ordering events equally likely. The proof uses the fact that the joint distribution is unchanged by relabeling, which follows from identical distributions as well as independence.

Key takeaway: For an iid sample with no ties, each of the $n!$ rank permutations has probability $1/n!$. Any event described solely by rank permutations can therefore be evaluated by counting its compatible permutations and dividing by $n!$.

Check Your Understanding

Use the uniform-permutation result and show your counting steps.

For $n=4$, what is the probability that $R_1=1$ and $R_2=2$?
For $n=5$, what is the probability that $X_3<X_1$, with no restriction on the other observations?
For $n=6$, how many rank permutations satisfy $R_1<R_2<R_3$? What is the probability of this event?
Why does uniformity of the rank vector not imply that $R_1,\ldots,R_n$ are independent?
Which feature of the iid assumption is used to show that all strict ordering events have equal probability?