Order statistics: maxima, minima and the gaps between

Questions about the largest, the smallest or the $k$ -th of several draws look like they need integration and almost never do. The maximum is easy because "all of them are below $x$ " factorises; the minimum is easy for the same reason; and the expectations for uniforms follow a pattern worth memorising outright.

Equation 5.1

The two that factorise

The maximum is below $x$ exactly when every draw is; the minimum is above $x$ exactly when every draw is.

F_{\max}(x) = F(x)^n, \qquad F_{\min}(x) = 1 - \big(1 - F(x)\big)^n

$F$: The common CDF of the independent draws.
$1 - F$: The survival function — start here for a minimum and the algebra is shorter.

Proposition 5.2

Uniforms on $[0,1]$ : the pattern

For $n$ independent uniforms on the unit interval, the $k$ -th smallest has expectation $k/(n+1)$ . So the minimum is $1/(n+1)$ , the maximum is $n/(n+1)$ , and the expected range is $(n-1)/(n+1)$ . Everything else about this family is a consequence.

Holds when

The $n$ points cut $[0,1]$ into $n+1$ gaps, and by symmetry each gap has expectation $1/(n+1)$ .
That symmetry — not any integral — is the fastest route to the whole set of answers.
On $[0, L]$ multiply everything by $L$ .

Why the gaps are all equal. Drop $n$ points on a circle of circumference one, then cut the circle at one marked point: you have $n$ points on a unit interval and $n+1$ gaps. Rotating the circle changes nothing about the distribution, so every gap has the same expectation, and they sum to one. That single picture gives $\mathbb{E}[\min]$ , $\mathbb{E}[\max]$ , the expected range and the expected distance between any two neighbouring order statistics — with no calculus anywhere.

Below the smallest — 20 of 100
First gap — 20 of 100
Second gap — 20 of 100
Third gap — 20 of 100
Above the largest — 20 of 100

Figure 5.3 · Four points cut the interval into five equal pieces. Read as five bands of twenty. Four uniform points make five gaps, and by the rotation argument each has the same expected length

1/5

— which puts the

k

-th smallest at

k/5

, so the minimum sits at

0.2

and the maximum at

0.8

.

Proposition 5.4

The minimum of exponentials

If $X_i \sim \text{Exp}(\lambda_i)$ independently, the minimum is exponential with rate $\sum \lambda_i$ , and the probability that $X_j$ is the smallest is $\lambda_j / \sum \lambda_i$ . Competing Poisson processes merge into one at the summed rate, and which one fires first is independent of when.

Holds when

This is why "which of these arrives first, and how long until something arrives" are separate, independent questions.
Memorylessness means waiting does not change the answer, which is what makes queueing and first-passage questions tractable.

Example 5.5

Three independent uniforms are drawn on $[0,1]$ . What are the expected maximum, the expected minimum, and the expected gap between the largest two?

Show the worked solutionHide the worked solution

Worked solution

Formula $\mathbb{E}[X_{(k)}] = \frac{k}{n+1}$
Substitute $n = 3$
Solve $\mathbb{E}[\max] = \tfrac34, \quad \mathbb{E}[\min] = \tfrac14$
$\mathbb{E}[X_{(3)} - X_{(2)}] = \tfrac34 - \tfrac24 = \tfrac14$
Answer $\tfrac34,\ \tfrac14,\ \tfrac14$

Sanity check. The four gaps — below the minimum, between each pair, and above the maximum — each come to $1/4$ and sum to one, exactly as the circle argument requires.

Order statistics: maxima, minima and the gaps between

After this lesson you should be able to

The two that factorise

Uniforms on $[0,1]$ : the pattern

The minimum of exponentials

The rest of this lesson is in Premium