Probability

Lesson 13 of 14

Order Statistics: The Biggest of Many

The distribution of the max, the min and the k-th smallest of n draws, the n+1 spacings that uniform points cut a stick into, and how slowly the best of many normals grows.

The max is below t only if everyone is

Sort nn i.i.d. draws X1,…,XnX_1, \dots, X_n from smallest to largest and write them X(1)≤X(2)≤⋯≤X(n)X_{(1)} \le X_{(2)} \le \cdots \le X_{(n)}. These are the order statistics. X(1)X_{(1)} is the minimum, X(n)X_{(n)} is the maximum, and for odd nn the middle one is the sample median.

The maximum is the easy one. The largest draw is at most tt exactly when every draw is at most tt, and independence lets you multiply:

P(X(n)≤t)=F(t)nP(X_{(n)} \le t) = F(t)^n

The minimum goes through its upper tail. The smallest draw is above tt exactly when every draw is:

P(X(1)>t)=(1−F(t))nP(X_{(1)} > t) = (1 - F(t))^n

Roll three fair dice and take the highest face. P(max⁡≤k)=(k/6)3P(\max \le k) = (k/6)^3, so P(max⁡≥k)=1−((k−1)/6)3P(\max \ge k) = 1 - ((k-1)/6)^3, and the tail-sum formula from the lesson on Infinite Expectations gives

E[max⁡]=∑k=16(1−(k−16)3)=6−0+1+8+27+64+125216=11924≈4.96E[\max] = \sum_{k=1}^{6} \left(1 - \left(\tfrac{k-1}{6}\right)^3\right) = 6 - \frac{0 + 1 + 8 + 27 + 64 + 125}{216} = \frac{119}{24} \approx 4.96

The expected minimum is 7−11924=4924≈2.047 - \frac{119}{24} = \frac{49}{24} \approx 2.04, because 7−X7 - X turns each die upside down and swaps the max with the min.

For exponentials the minimum formula gives a clean answer. If Xi∼Exponential(λi)X_i \sim \text{Exponential}(\lambda_i) are independent, then P(min⁡>t)=∏ie−λit=e−(λ1+⋯+λn)tP(\min > t) = \prod_i e^{-\lambda_i t} = e^{-(\lambda_1 + \cdots + \lambda_n)t}, so the minimum is exponential with the rates added. Five servers each fail after an exponential time with mean 10 hours (rate 0.1). The first failure is Exponential(0.5), so it comes after 2 hours on average.