Order Statistics and Their Joint Distribution

Why Sorting Changes the Joint Distribution

A random sample is usually recorded in the order its observations are collected. But many statistics describe the observations after sorting them: the smallest value, the next-smallest value, and so on. To find probabilities involving these ordered values, we need to account for the fact that sorting discards the original labels while preserving the values.

For an independent, identically distributed (IID) sample from a continuous population, the joint density of the sorted observations has a simple form. It is the original product density, restricted to increasing values, multiplied by the number of ways the original observations could have been assigned to those values.

Definition: Let \(X_1,\ldots,X_n\) be a sample, and arrange the observed values in increasing order. The resulting random variables are the order statistics: \(X_{(1)}\leq X_{(2)}\leq\cdots\leq X_{(n)}\). Here \(X_{(1)}\) is the smallest sample value, \(X_{(n)}\) is the largest, and \(X_{(k)}\) is the \(k\)th-smallest value. For a continuous population, ties have probability zero, so the inequalities are strict with probability one.

The Joint Density of All Order Statistics

Assume \(X_1,\ldots,X_n\) are IID from a continuous distribution with probability density function \(f\), and that the density is supported on an interval \(I\). Before sorting, the sample has joint density \(f(x_1)\cdots f(x_n)\), by independence. After sorting, the possible vectors are restricted to \(x_1<x_2<\cdots<x_n\).

Theorem: Under the IID continuous model above, the joint density of \((X_{(1)},\ldots,X_{(n)})\) is \[ f_{X_{(1)},\ldots,X_{(n)}}(x_1,\ldots,x_n) = \begin{cases} n!\displaystyle\prod_{i=1}^{n} f(x_i), & x_1<x_2<\cdots<x_n,\quad x_i\in I,\\ 0, & \text{otherwise.} \end{cases} \]

The factor \(n!\) is the number of possible assignments of the \(n\) distinct sample labels to a given strictly ordered set of values. The density is zero outside the ordered region because sorted observations cannot occur in any other arrangement. To calculate a probability for the order statistics, integrate this density over the part of the ordered region that satisfies the event.

Why the Factor Is \(n!\)

For a strictly increasing vector \(x_1<\cdots<x_n\), there are \(n!\) ways to assign the original labels \(1,\ldots,n\) to those ordered values. For example, with three values, the original sample could have been \((x_1,x_2,x_3)\), \((x_2,x_1,x_3)\), or any of the other four permutations. Each assignment has the same density contribution because the observations are identically distributed.

More formally, sorting divides the original sample space, except for tie cases of probability zero, into \(n!\) regions corresponding to the possible label orderings. On each region, sorting is a permutation of coordinates. A coordinate permutation has Jacobian determinant with absolute value \(1\), so it does not change the density volume. Since each permutation has original density \(\prod_{i=1}^n f(x_i)\), their contributions add to \(n!\prod_{i=1}^n f(x_i)\).

\sum_{\text{permutations}} \prod_{i=1}^{n} f(x_i) = n!\prod_{i=1}^{n} f(x_i), \qquad x_1<x_2<\cdots<x_n.

The IID and continuous assumptions matter. If the observations are independent but have different density functions, the contributions from the permutations need not be equal, so the factor \(n!\) times one product is generally not correct. If the population is discrete, ties can have positive probability and a density on the strict-order region does not describe the full distribution.

Worked Example: A Uniform Sample in Three Separate Ranges

Suppose a hypothetical laboratory samples three independent measurement errors \(X_1,X_2,X_3\), each uniformly distributed on \((0,1)\). Find the probability that \(X_{(1)}\) is between \(0.1\) and \(0.3\), \(X_{(2)}\) is between \(0.5\) and \(0.7\), and \(X_{(3)}\) is between \(0.8\) and \(1\).

Model and method. The observations are IID Uniform\((0,1)\), so \(f(x)=1\) for \(0<x<1\). The joint density of the three order statistics is \(3!=6\) on \(0<x_1<x_2<x_3<1\). The three specified intervals are already separated in increasing order, so every choice of one value from each interval satisfies the ordering.

Integrate over the event. The event region is a rectangular box inside the ordered region. Its side lengths are \(0.3-0.1=0.2\), \(0.7-0.5=0.2\), and \(1-0.8=0.2\). Therefore,

P(0.1<X_{(1)}<0.3,\ 0.5<X_{(2)}<0.7,\ 0.8<X_{(3)}<1) =6(0.2)(0.2)(0.2)=0.048.

Check. The probability is \(0.048\), which is less than \(1\), as required. The common mistake is to use only the probability for one original labeling, \((0.2)^3=0.008\), and omit the six possible assignments of the original sample labels to the three ordered ranges.

Probability Calculations Require the Ordered Region

Not every event for order statistics is a rectangular box with separated intervals. When the event places bounds on only some order statistics, the remaining coordinates must still satisfy the ordering. The integration limits must encode both the event and the condition \(x_1<\cdots<x_n\).

Worked Example: Exponential Observations in Ordered Intervals

A hypothetical monitoring system records two independent waiting times \(X_1,X_2\), each exponentially distributed with rate \(\lambda=1\) per hour. Find the probability that the smaller waiting time is between \(0\) and \(1\) hour and the larger is between \(2\) and \(3\) hours.

Model and method. The density is \(f(x)=e^{-x}\) for \(x>0\). The ordered pair has density \(2e^{-(x_1+x_2)}\) on \(0<x_1<x_2\). The event is \(0<X_{(1)}<1\) and \(2<X_{(2)}<3\); since the intervals do not overlap, the ordering is automatic throughout this event.

Integrate. The density factors into a function of \(x_1\) times a function of \(x_2\), and the event is a rectangle:

\begin{aligned} P(0<X_{(1)}<1,\ 2<X_{(2)}<3) &=2\int_0^1 e^{-x_1}\,dx_1\int_2^3 e^{-x_2}\,dx_2\\ &=2(1-e^{-1})(e^{-2}-e^{-3})\\ &\approx 2(0.6321)(0.08555)\\ &\approx 0.1082. \end{aligned}

Check. The probability is approximately \(0.1082\), to four decimal places. The same result can be checked from the original sample: either \(X_1\) is in \((0,1)\) and \(X_2\) is in \((2,3)\), or their labels are reversed. Those two disjoint cases have equal probability, explaining the factor of \(2\). Forgetting the reversed labeling would give half the answer.

Worked Example: Integrating Over a Triangular Ordered Region

Suppose \(X_1,X_2,X_3\) are IID Uniform\((0,2)\). Find the probability that the middle ordered observation is less than \(1\), that is, \(X_{(2)}<1\).

Model and method. The original density is \(1/2\) on \((0,2)\). Thus the joint density of the three order statistics is \(3!(1/2)^3=6/8=3/4\) on \(0<x_1<x_2<x_3<2\).

Set the limits. The event requires \(0<x_2<1\). Given \(x_2\), the ordering requires \(0<x_1<x_2\) and \(x_2<x_3<2\). Hence the probability is an integral over a nonrectangular region:

\begin{aligned} P(X_{(2)}<1) &=\frac{3}{4}\int_0^1\int_0^{x_2}\int_{x_2}^{2} dx_3\,dx_1\,dx_2\\ &=\frac{3}{4}\int_0^1 x_2(2-x_2)\,dx_2\\ &=\frac{3}{4}\left[x_2^2-\frac{x_2^3}{3}\right]_0^1\\ &=\frac{3}{4}\left(1-\frac{1}{3}\right) =\frac{1}{2}. \end{aligned}

The middle line follows because integrating \(1\) over \(x_3\) from \(x_2\) to \(2\) gives \(2-x_2\), and integrating over \(x_1\) from \(0\) to \(x_2\) gives \(x_2\). Check. The result is \(1/2\), consistent with the symmetry of three IID observations from a distribution split into equal-probability intervals \((0,1)\) and \((1,2)\): the middle observation is below \(1\) precisely when at least two of the three observations are below \(1\), which has probability \(\binom{3}{2}(1/2)^3+(1/2)^3=1/2\). The trap is to integrate \(x_3\) over \((0,2)\) without enforcing \(x_3>x_2\), which would include points outside the ordered region.

Interpretation and Common Traps

The original observations are independent, but their order statistics are generally not independent. For example, with two IID Uniform\((0,1)\) observations, the ordered pair has density \(2\) only when \(0<x_1<x_2<1\). Its support is triangular, not the rectangular support that independent variables with separate ranges would have. Knowing one ordered value restricts which values the other can take.

The joint density is also a density with respect to all \(n\) coordinates together. A density value can exceed \(1\); it is an infinitesimal rate, not a probability at a point. Probabilities come from integrating over regions. For instance, in the Uniform\((0,1)\) sample of size three, the joint density is \(6\), while the total probability is \(6\) times the volume \(1/6\) of the ordered simplex, which equals \(1\).

Do not omit \(n!\). A particular ordered vector can arise from any of \(n!\) label assignments in the original IID sample.
Do not use the formula outside its support. The density is zero unless the coordinates are in the population support and in increasing order.
Do not assume sorted values remain independent. Their joint support and density impose ordering constraints.
Do not apply the formula unchanged to discrete data or nonidentically distributed observations. Ties or unequal permutation contributions require a different treatment.

The joint-density approach is useful whenever an event constrains several sorted observations at once. The key steps are to state the IID continuous model, write the density on the ordered region, translate the event into integration limits, and retain every ordering constraint in those limits.

Check Your Understanding

For each problem, identify the ordered region before calculating.

Let \(X_1,X_2\) be IID Uniform\((0,1)\). Find \(P(0.1<X_{(1)}<0.3,\ 0.6<X_{(2)}<0.9)\). (Answer: \(0.12\))
Let \(X_1,X_2,X_3\) be IID Uniform\((0,1)\). Find the probability that the three ordered values fall respectively in \((0.1,0.2)\), \((0.4,0.5)\), and \((0.7,0.9)\). (Answer: \(0.012\))
Let \(X_1,X_2\) be IID exponential with rate \(\lambda=2\) per hour. Evaluate the joint density of \((X_{(1)},X_{(2)})\) at \((0.2,0.6)\). (Answer: \(8e^{-1.6}\approx 1.615\) per square hour)
Let \(X_1,X_2,X_3\) be IID Uniform\((0,3)\). Find \(P(X_{(1)}<1,\ 1<X_{(2)}<2)\), with no further restriction on \(X_{(3)}\) beyond its required ordering and population support. (Answer: \(1/3\))

What You'll Learn