Independence of Ranks and Order Statistics

Why Separate the Labels From the Sorted Values?

Sorting a sample changes its order but does not change its values. It is useful to keep track of these two pieces of information separately: the ordered values tell us where the observations lie, while the permutation tells us which sample label occupies each position. Under iid sampling from a continuous density, the permutation is not only uniform; it is independent of the ordered values. Thus, knowing the sorted values does not favor any particular assignment of sample labels to ranks.

This distinction matters when a calculation involves both the magnitudes of observations and their labels. The result below supplies a precise factorization for such calculations. Its key reason is symmetry: each possible ordering has the same joint density when expressed in terms of the ordered values.

Definitions and Main Result

Definition: Let $X_1,\ldots,X_n$ be a sample with no ties, and write its ordered values as $X_{(1)}<\cdots<X_{(n)}$. Define the sorting permutation $\Pi$ by $X_{\Pi(j)}=X_{(j)}$ for $j=1,\ldots,n$. Thus, $\Pi(j)$ is the sample label occupying rank $j$. The rank vector $R=(R_1,\ldots,R_n)$, where $R_i$ is the rank of $X_i$, is the inverse-permutation encoding: $R_i=j$ exactly when $\Pi(j)=i$.

A random vector with a density has probability zero of falling on any specified hyperplane. In particular, when the observations are independent and each has a density, $P(X_i=X_j)=0$ for $i\ne j$; a finite union over pairs shows that ties have probability zero. The strict ordering above is therefore well-defined with probability one.

Theorem: Suppose $X_1,\ldots,X_n$ are iid with common Lebesgue density $f$. Then the sorting permutation $\Pi$ is independent of $(X_{(1)},\ldots,X_{(n)})$. Moreover, $\Pi$ is uniform over the $n!$ permutations, and for every measurable set $B$ in the ordered region, $$ P\bigl(\Pi=\pi,\ (X_{(1)},\ldots,X_{(n)})\in B\bigr) =\frac{1}{n!}P\bigl((X_{(1)},\ldots,X_{(n)})\in B\bigr). $$

Here the ordered region is $C=\{(u_1,\ldots,u_n):u_1<\cdots<u_n\}$. The rank vector $R$ is also independent of the ordered values: it is a one-to-one deterministic encoding of $\Pi$, so events specified by $R$ correspond exactly to events specified by $\Pi$.

Proof by Partitioning the Joint Density

Independence and the common density give the joint density $f(x_1)\cdots f(x_n)$ for the original labelled sample. Except on the probability-zero tie set, the sample space is partitioned into $n!$ regions, one for each possible sorting permutation. On the region corresponding to $\pi$, set $x_{\pi(j)}=u_j$ for $j=1,\ldots,n$. This is a coordinate permutation, whose Jacobian has absolute value one. The joint density in the $u$ coordinates is therefore $\prod_{j=1}^n f(u_j)$, the same for every $\pi$.

Fix a permutation.
For any measurable $B\subseteq C$, the event that the ordered values lie in $B$ and $\Pi=\pi$ corresponds, up to ties, to the labelled sample region $x_{\pi(1)}<\cdots<x_{\pi(n)}$ with ordered coordinate vector in $B$.

Integrate on that region.
The coordinate change $x_{\pi(j)}=u_j$ has absolute Jacobian one. Independence and identical distributions give $$ P\bigl(\Pi=\pi,\ (X_{(1)},\ldots,X_{(n)})\in B\bigr) =\int_B\prod_{j=1}^n f(u_j)\,du_1\cdots du_n. $$

Sum over all permutations.
The $n!$ regions are disjoint except for ties, which have probability zero. Each contributes the same integral, so $$ P\bigl((X_{(1)},\ldots,X_{(n)})\in B\bigr) =n!\int_B\prod_{j=1}^n f(u_j)\,du_1\cdots du_n. $$

Factor the joint probability.
Combining the two expressions gives the theorem’s identity. Taking $B=C$ gives $P(\Pi=\pi)=1/n!$. For arbitrary measurable $B\subseteq C$, the joint probability equals $P(\Pi=\pi)P((X_{(1)},\ldots,X_{(n)})\in B)$, which is the definition of independence. $\square$

The same calculation also gives the joint density of the ordered values on $C$: it is $n!\prod_{j=1}^n f(u_j)$. The factor $n!$ appears because all $n!$ labelled regions map to the same ordered region and contribute equal integrals. Independence follows from the factorization, not merely from the fact that the permutation has equal marginal probabilities.

Worked Examples

Worked Example: Three Uniform Observations

Let $X_1,X_2,X_3$ be iid Uniform$(0,1)$, and consider the event $B=\{X_{(2)}\le 1/2\}$. Find $P(\Pi=(2,1,3),\,B)$ and check the independence factorization.

The ordered density is $3!=6$ on $0<u_1<u_2<u_3<1$. Hence $$ P(B)=6\int_0^{1/2}\int_0^{u_2}\int_{u_2}^1du_3\,du_1\,du_2 =6\int_0^{1/2}u_2(1-u_2)\,du_2. $$

Evaluating the integral, $$ P(B)=6\left[\frac{u_2^2}{2}-\frac{u_2^3}{3}\right]_0^{1/2} =6\left(\frac18-\frac1{24}\right)=\frac12. $$

For one specified permutation, the joint density on the ordered region is $1$, not $6$: the factor $6$ in the ordered density sums across the six possible permutations. Therefore $$ P(\Pi=(2,1,3),\,B) =\int_0^{1/2}u_2(1-u_2)\,du_2 =\frac1{12}. $$ Since $P(\Pi=(2,1,3))=1/6$, the product of the marginal probabilities is $(1/6)(1/2)=1/12$, matching the joint probability.

Worked Example: Exponential Order Statistics

Let $X_1,X_2$ be iid exponential observations with rate $\lambda>0$, so $f(x)=\lambda e^{-\lambda x}$ for $x>0$. For $c\ge 0$, find the probability that $X_1<X_2$ and $X_{(1)}>c$.

In ordered coordinates $c<u<v$, the event $X_1<X_2$ specifies one permutation. Its probability is $$ \begin{aligned} P(X_1<X_2,\ X_{(1)}>c) &=\int_c^\infty\int_u^\infty \lambda^2e^{-\lambda(u+v)}\,dv\,du\\ &=\int_c^\infty\lambda e^{-\lambda u}e^{-\lambda u}\,du\\ &=\int_c^\infty\lambda e^{-2\lambda u}\,du =\frac12e^{-2\lambda c}. \end{aligned} $$

The event $X_{(1)}>c$ means both observations exceed $c$, so independence of the original observations gives $P(X_{(1)}>c)=e^{-\lambda c}e^{-\lambda c}=e^{-2\lambda c}$. The permutation has probability $1/2$, and the joint probability is exactly half of this order-statistic probability, as the theorem predicts.

Worked Example: Why Identical Distributions Matter

Let $X_1\sim\operatorname{Uniform}(0,1)$ and $X_2\sim\operatorname{Uniform}(0,2)$, independently. Set $A=\{X_1<X_2\}$ and $B=\{X_{(1)}>1/2\}$. These observations have densities, but are not identically distributed.

First, $$ P(A)=\int_0^1P(X_2>x)\,dx =\int_0^1\left(1-\frac{x}{2}\right)dx =\frac34. $$ Also, $$ P(B)=P(X_1>1/2)P(X_2>1/2) =\frac12\cdot\frac34=\frac38. $$

For both $A$ and $B$ to occur, $1/2<X_1<1$ and $X_1<X_2<2$. The joint density on this region is $1\cdot(1/2)=1/2$, so $$ P(A\cap B)=\int_{1/2}^1\int_{x_1}^2\frac12\,dx_2\,dx_1 =\int_{1/2}^1\left(1-\frac{x_1}{2}\right)dx_1 =\frac5{16}. $$

But $P(A)P(B)=(3/4)(3/8)=9/32$, whereas $5/16=10/32$. Thus $A$ and $B$ are not independent. The equal contribution from every permutation in the proof depended on the common density $f$; independence alone, without identical distributions, does not provide that symmetry.

Conditional Interpretation and Common Pitfalls

The factorization has a useful conditional interpretation. For almost every ordered vector $u$ with positive ordered density, each permutation has the same conditional probability, $1/n!$, given those ordered values. This statement is understood through a conditional distribution: it does not mean that the probability of observing any one exact continuous vector $u$ is positive. Rather, the joint density for each permutation at $u$ is $\prod_j f(u_j)$, while the ordered density is $n!\prod_j f(u_j)$; their ratio is $1/n!$ wherever the denominator is positive.

Equal marginal probabilities do not by themselves prove independence. Uniformity of $\Pi$ says each permutation has probability $1/n!$. Independence additionally requires the joint factorization for every measurable set of ordered values.
Do not omit the identical-distribution assumption. Independent observations with different densities can favor some label orderings in some parts of the ordered-value space, as the third example shows.
Keep the permutation convention clear. Here $\Pi(j)$ is the label at rank $j$. The rank vector records the inverse mapping. Confusing these conventions can reverse an event’s description, even though both encode the same ordering.
Check ties before defining strict ranks. A common density ensures ties have probability zero. If a model has atoms, tied observations may occur and the strict-permutation argument needs a different treatment.

Key takeaway: For iid observations with a common density, every labelled ordering contributes the same density to the ordered values. The resulting factor of $1/n!$ proves that the rank permutation is uniform and independent of the order statistics.

Check Your Understanding

Use the definitions and density factorization to answer the following questions.

For $n=4$, what is the probability of any one specified sorting permutation?
Why does the coordinate transformation from labelled observations to ordered values have Jacobian with absolute value one?
For iid observations with a density, explain why the joint density of the ordered values contains a factor of $n!$.
In the exponential example, what is $P(X_1<X_2,\ X_{(1)}>c)$ when $\lambda=2$ and $c=1$?
Which assumption fails in the example with $X_1\sim\operatorname{Uniform}(0,1)$ and $X_2\sim\operatorname{Uniform}(0,2)$, and how does that failure affect the proof?