Order Statistics From Uniform Variates

Why Order Statistics Matter in Simulation

A simulation may need more than an unordered collection of random values. An insurer might be interested in the smallest or largest claim in a hypothetical sample, or in a claim at a specified rank. These quantities are order statistics. They are obtained by sorting the simulated observations, but their probability distributions can also be derived directly.

This tutorial uses independent uniform variates to generate and analyze order statistics. The assumptions are that $U_1,\ldots,U_n$ are independent and each has the continuous uniform distribution on $(0,1)$. Under this model, ties have probability zero, so the sorted values are almost surely strictly ordered.

Definition: Write the observations in increasing order as $U_{(1)}\le U_{(2)}\le\cdots\le U_{(n)}$. The value $U_{(k)}$ is the $k$th order statistic. In particular, $U_{(1)}=\min(U_1,\ldots,U_n)$ and $U_{(n)}=\max(U_1,\ldots,U_n)$.

Sorting a set of independent uniform draws is the direct method for generating the full ordered sample. If only the minimum or maximum is required, a transformation of one uniform draw can generate the correct marginal distribution more efficiently. These methods have different purposes: one transformed draw generates one extreme with the right distribution, while sorting a sample preserves the joint relationships among all its ranks.

Distributions of the Minimum and Maximum

For $0\le u\le1$, the minimum exceeds $u$ precisely when every observation exceeds $u$. Independence therefore gives

P(U_{(1)}>u)=P(U_1>u,\ldots,U_n>u)=(1-u)^n.

Consequently, the cumulative distribution function of the minimum is $1-(1-u)^n$. The maximum is at most $u$ precisely when every observation is at most $u$, so its cumulative distribution function is $u^n$.

Result: For $0\le u\le1$, $$ F_{U_{(1)}}(u)=1-(1-u)^n,\qquad F_{U_{(n)}}(u)=u^n. $$ Their densities on $(0,1)$ are $f_{U_{(1)}}(u)=n(1-u)^{n-1}$ and $f_{U_{(n)}}(u)=nu^{n-1}$, respectively.

To simulate a minimum with the correct distribution, let $R\sim\operatorname{Uniform}(0,1)$ and set $R=1-(1-u)^n$, solving for $u$. For a maximum, set $R=u^n$ and solve. These transformations work because the resulting cumulative distribution function evaluated at the simulated value equals $R$, which is uniform.

U_{(1)}=1-(1-R)^{1/n},\qquad U_{(n)}=R^{1/n}.

Each formula generates the correct distribution for its stated order statistic, but using separate random numbers in these formulas does not generate the minimum and maximum of the same sample. For a jointly correct pair of extremes, generate $n$ independent uniforms and take their minimum and maximum, or use a method based on their joint distribution.

The Distribution of a General Rank

Fix $k$ between 1 and $n$. The event $U_{(k)}\le u$ occurs exactly when at least $k$ of the $n$ observations are at most $u$. The number of observations at most $u$ has a binomial distribution with $n$ trials and success probability $u$. Thus

F_{U_{(k)}}(u) =P(U_{(k)}\le u) =\sum_{j=k}^{n}\binom{n}{j}u^j(1-u)^{n-j}, \qquad 0\le u\le1.

This count-based expression gives a direct way to calculate order-statistic probabilities. Differentiating it gives the density. To see the simplification, differentiate each term. The positive derivative contribution from the $j$th term is $j\binom{n}{j}u^{j-1}(1-u)^{n-j}$; the negative contribution is $-(n-j)\binom{n}{j}u^j(1-u)^{n-j-1}$. Using $j\binom{n}{j}=n\binom{n-1}{j-1}$ and $(n-j)\binom{n}{j}=n\binom{n-1}{j}$, the negative contribution at one index cancels the positive contribution at the next index. Only the first positive term remains. Therefore,

f_{U_{(k)}}(u) =\frac{n!}{(k-1)!(n-k)!}\,u^{k-1}(1-u)^{n-k}, \qquad 0<u<1.

This is a beta density with parameters $k$ and $n+1-k$. In particular, substituting $k=1$ or $k=n$ recovers the minimum and maximum densities above. The mean and variance are

E[U_{(k)}]=\frac{k}{n+1},\qquad \operatorname{Var}(U_{(k)}) =\frac{k(n+1-k)}{(n+1)^2(n+2)}.

These moment formulas follow by integrating the density. In beta-integral notation, the density is $u^{k-1}(1-u)^{n-k}/B(k,n+1-k)$, where $B(a,b)=\int_0^1 u^{a-1}(1-u)^{b-1}\,du$. The ratio of integrals gives $E[U_{(k)}]=B(k+1,n+1-k)/B(k,n+1-k)=k/(n+1)$. Applying the same relation to the second moment gives $E[U_{(k)}^2]=k(k+1)/((n+1)(n+2))$; subtracting the square of the mean yields the stated variance.

Generating the Full Sorted Sample

When all ranks are needed, the procedure is simple: generate $n$ independent uniform values, then sort them in increasing order. Do not replace the sorted vector with independently generated order statistics. Although each rank has a known marginal distribution, the ranks are dependent: for example, $U_{(1)}\le U_{(2)}$ always.

Generate the sample.
Draw $U_1,\ldots,U_n$ independently from $\operatorname{Uniform}(0,1)$.

Sort the values.
Arrange the generated values in nondecreasing order.

Read the requested rank.
The smallest is $U_{(1)}$, the largest is $U_{(n)}$, and the $k$th smallest is $U_{(k)}$.

If a continuous, strictly increasing distribution function $F_X$ is being simulated by inverse transformation, applying $F_X^{-1}$ to each uniform value preserves the ordering. Thus the $k$th ordered simulated value is $F_X^{-1}(U_{(k)})$. This statement requires the same sample of uniforms to be sorted; it does not mean that separately generated ranks can be combined into a sorted sample.

Worked Example: Sorting a Hypothetical Uniform Sample

A hypothetical simulation produces five independent uniform values: $0.58,\ 0.14,\ 0.93,\ 0.31,\ 0.76$. Find the ordered sample, the minimum, the maximum, and the expected value and variance of the sample median under the assumed model.

Method. Sort the five draws, then use the order-statistic moment formulas with $n=5$ and $k=3$ for the median. This avoids confusing the rank with the original draw order.

Sort the observations. In increasing order they are $0.14,\ 0.31,\ 0.58,\ 0.76,\ 0.93$. Therefore $U_{(1)}=0.14$, $U_{(3)}=0.58$, and $U_{(5)}=0.93$.

Calculate the theoretical median moments. Here $n+1=6$, so $E[U_{(3)}]=3/6=0.5$. Its variance is \[ \operatorname{Var}(U_{(3)}) =\frac{3(6-3)}{6^2(7)} =\frac{9}{252} =\frac{1}{28} \approx0.035714. \] The observed median is $0.58$; the theoretical mean is $0.5$. The observed value need not equal the mean in a particular simulation.

Check. The sorted values contain all five original draws, and $0.14\le0.31\le0.58\le0.76\le0.93$, as required. The median is the third value, not the third value in the unsorted list.

Worked Example: Generating an Extreme Directly

A hypothetical simulation needs only the minimum of eight independent uniform draws. The random-number generator supplies $R=0.83222784$. Generate a value with the distribution of that minimum. Separately, find the maximum generated from an input $R=0.16777216$ for a sample of size eight.

Method. Use the inverse cumulative distribution transformation for the minimum and maximum. Each input is a uniform variate; the outputs have the relevant marginal extreme-value distributions.

For the minimum, $1-R=1-0.83222784=0.16777216=0.8^8$. Hence \[ U_{(1)}=1-(1-R)^{1/8}=1-(0.8^8)^{1/8}=1-0.8=0.2. \]

For the maximum, $R=0.16777216=0.8^8$, so \[ U_{(8)}=R^{1/8}=(0.8^8)^{1/8}=0.8. \]

Check. The minimum has cumulative probability $1-(1-0.2)^8=1-0.8^8=0.83222784$, equal to its input. The maximum has cumulative probability $0.8^8=0.16777216$, also equal to its input. These two outputs are generated from separate inputs and are not a jointly generated minimum-maximum pair.

Worked Example: Probability for the Second Order Statistic

For a hypothetical sample of five independent uniform draws, calculate $P(U_{(2)}\le0.4)$, and find the mean and variance of $U_{(2)}$.

Method. Count the observations at most $0.4$. The event $U_{(2)}\le0.4$ requires at least two such observations. The count has a binomial distribution with $n=5$ and success probability $0.4$.

It is simpler to subtract the cases with zero or one observation at most $0.4$: \[ P(U_{(2)}\le0.4) =1-P(\text{count}=0)-P(\text{count}=1). \] The two probabilities are \[ P(\text{count}=0)=0.6^5=0.07776,\qquad P(\text{count}=1)=\binom51(0.4)(0.6)^4=5(0.4)(0.1296)=0.2592. \] Therefore, \[ P(U_{(2)}\le0.4)=1-0.07776-0.2592=0.66304. \]

For $n=5,\ k=2$, the mean is $2/(5+1)=1/3$. The variance is \[ \operatorname{Var}(U_{(2)}) =\frac{2(6-2)}{6^2(7)} =\frac{8}{252} =\frac{2}{63} \approx0.031746. \]

Check. The event is not that exactly two observations are at most $0.4$; it includes counts of two, three, four, and five. Subtracting only the zero- and one-count cases includes all those possibilities.

Common Exam Trap: Confusing Marginals With a Joint Sample

A frequent error is to generate the minimum and maximum independently from their correct individual formulas and treat them as if they came from the same sample. Correct marginal distributions do not guarantee a correct joint distribution. In a sample, the minimum must be less than or equal to the maximum, and their values are dependent.

For example, with three uniform observations, the probability that the minimum exceeds $0.2$ and the maximum is below $0.8$ is the probability that all three observations lie between $0.2$ and $0.8$: \[ P(U_{(1)}>0.2,\ U_{(3)}<0.8)=(0.8-0.2)^3=0.216. \] The product of the separate probabilities would instead be \[ P(U_{(1)}>0.2)P(U_{(3)}<0.8) =(0.8^3)(0.8^3)=0.262144, \] which is not the joint probability. The correction is to account for the shared sample, as in the all-observations-in-the-interval calculation, or to generate and sort that sample directly.

Key takeaway: Sort independent uniform draws when you need a complete ordered sample or jointly related ranks. Use the one-uniform transformation for a minimum or maximum only when its marginal distribution is all that is required. For a general rank, use the binomial count interpretation of $U_{(k)}\le u$.

Check Your Understanding

Use independent $\operatorname{Uniform}(0,1)$ draws in each question unless stated otherwise.

For a sample of four, calculate the probability that its minimum exceeds $0.25$. (Answer: $0.75^4=0.3164$)
For a sample of seven, a direct maximum simulation uses input $R=0.8^7=0.2097152$. What maximum value does the transformation produce? (Answer: $0.8$)
For a sample of six, calculate $P(U_{(2)}\le0.3)$. (Answer: $1-0.7^6-6(0.3)(0.7^5)=0.5798$)
For a sample of eight, give the mean and variance of $U_{(4)}$. (Answer: mean $4/9$; variance $2/81$)
For a sample of three, calculate $P(U_{(1)}>0.2,\ U_{(3)}<0.8)$, and explain why multiplying the two marginal probabilities is incorrect. (Answer: $0.6^3=0.216$; the events depend on the same three observations.)

What You'll Learn