Order Statistics

Given $n$ random variables $X_1, \ldots, X_n$, the order statistics are the sorted values $X_{(1)} \le X_{(2)} \le \cdots \le X_{(n)}$. So $X_{(1)} = \min$, $X_{(n)} = \max$, and $X_{(k)}$ is the $k$-th smallest. The fundamental CDF: For $n$ i.i.d. draws from CDF $F$: $$P(X_{(k)} \le x) = \sum_{j=k}^{n} \binom{n}{j} [F(x)]^j [1 - F(x)]^{n-j}$$ Intuition: $X_{(k)} \le x$ means at least $k$ of the $n$ values fall at or below $x$, which is a binomial sum with success probability $F(x)$. Concrete example: Two players draw independently from Uniform$[0,1]$. What is $E[\max(X_1, X_2)]$? The CDF of the max is $P(X_{(2)} \le x) = x^2$, so the PDF is $2x$, giving: $$E[X_{(2)}] = \int_0^1 x \cdot 2x\, dx = \frac{2}{3}$$ More generally, for $n$ Uniform$[0,1]$ draws: $E[X_{(k)}] = \frac{k}{n+1}$. The Beta connection: For Uniform$[0,1]$ samples, $X_{(k)} \sim \text{Beta}(k, n-k+1)$. This is extremely useful in auction theory, where bidders draw values from a distribution and the highest or second-highest order statistic determines the outcome. When to use: Auction theory (revenue = function of order statistics), extreme value problems, best-of-$n$ scenarios, and any problem involving "the $k$-th largest draw."