Appendix: Order Statistics

Motivating Example: When Does the Meeting Start?¶

Five colleagues agree to meet during a one hour window. Each arrives at a time chosen independently and uniformly at random within the window. The room is unlocked as soon as the first person arrives, and the meeting starts only when the last person arrives.

Two natural questions follow. On average, how long does the room sit unlocked before the meeting starts? More precisely:

1. What is the expected arrival time of the first person?

2. What is the expected arrival time of the last person?

Both questions ask for the expected value of a ranked member of a random sample: the smallest arrival time and the largest. Quantities of this kind are called order statistics, and they can be computed exactly. This appendix develops the tools needed to do so, in particular for values drawn uniformly at random from an interval, which is the setting used in the Auction Games chapter.

Theory¶

Definition: Probability Density and Cumulative Distribution Functions¶

A continuous random variable $X$ has a probability density function (pdf) $f$ if for all $a \leq b$:

The cumulative distribution function (cdf) of $X$ is:

The two functions carry the same information: the cdf is the integral of the pdf, and wherever $F$ is differentiable, $F'(x) = f(x)$. The expected value of $X$ is:

Definition: The Uniform Distribution¶

A random variable $X$ is uniform on $[0, 1]$ if its pdf is $f(x) = 1$ for $x \in [0, 1]$ and 0 otherwise. Its cdf is:

Every value in $[0, 1]$ is equally likely, and the expected value is:

Theorem: Expectation via the Survival Function¶

If $X$ takes values in $[0, 1]$ with cdf $F$ then:

This follows from integration by parts:

since $F(1) = 1$ makes the boundary term vanish. The function $1 - F(x) = \mathbb{P}(X > x)$ is called the survival function, and this form of the expectation is often the quickest route to expected minima, as the next results show.

Definition: Order Statistics¶

Let $X_1, X_2, \dots, X_N$ be independent random variables, each with cdf $F$. The order statistics $X_{(1)} \leq X_{(2)} \leq \dots \leq X_{(N)}$ are the same values sorted into increasing order: $X_{(k)}$ is the $k$-th smallest of the sample. In particular:

Theorem: CDF of the Maximum and the Minimum¶

Let $X_1, \dots, X_N$ be independent, each with cdf $F$. Then:

The first statement holds because the maximum is at most $x$ precisely when every $X_i$ is at most $x$, and by independence these $N$ events have probability $F(x)^N$ jointly. Similarly the minimum exceeds $x$ precisely when every $X_i$ exceeds $x$, so $\mathbb{P}(\min_i X_i > x) = (1 - F(x))^N$, and the cdf of the minimum is the complement.

Example: Two Uniform Values¶

Let $v_1$ and $v_2$ be independent and uniform on $[0, 1]$. This is the setting of a two bidder auction with uniform valuations. We compute the expected values of $\max(v_1, v_2)$ and $\min(v_1, v_2)$.

The maximum. With $F(x) = x$ and $N = 2$ the cdf of the maximum is $F_{(2)}(x) = x^2$, so its pdf is $f_{(2)}(x) = 2x$ and:

The minimum. The survival function of the minimum is $\mathbb{P}(\min(v_1, v_2) > x) = (1 - x)^2$, so by expectation via the survival function:

As a check, $\min(v_1, v_2) + \max(v_1, v_2) = v_1 + v_2$, so the two expectations must sum to $\mathbb{E}[v_1] + \mathbb{E}[v_2] = 1$, and indeed $\frac{1}{3} + \frac{2}{3} = 1$. A further consequence, by linearity of expectation, is the expected gap between the two values:

Theorem: Expected Order Statistics of the Uniform Distribution¶

Let $X_1, \dots, X_N$ be independent and uniform on $[0, 1]$. The $k$-th order statistic has pdf:

and expected value:

The form of the pdf can be read off directly: for $X_{(k)}$ to sit at $x$, one of the $N$ values must land at $x$ (a factor of $N f(x) = N$), and of the remaining $N - 1$ values, some $k - 1$ must fall below $x$ (each with probability $x$) and the other $N - k$ above (each with probability $1 - x$), with $\binom{N - 1}{k - 1}$ ways to choose which. The expectation then follows from the Beta integral:

applied with $a = k$ and $b = N - k$:

The result has a pleasing interpretation: $N$ uniform points split $[0, 1]$ into $N + 1$ gaps, and by symmetry each gap has expected length $\frac{1}{N + 1}$. The expected order statistics are therefore evenly spaced: $\frac{1}{N + 1}, \frac{2}{N + 1}, \dots, \frac{N}{N + 1}$. Setting $k = 1$ and $k = N$ recovers the expected minimum and maximum:

This answers the questions of Motivating Example: When Does the Meeting Start?: with $N = 5$ colleagues, the room is unlocked at $\frac{1}{6}$ of the window on average (10 minutes in), and the meeting starts at $\frac{5}{6}$ (50 minutes in), so the room sits unlocked for an expected 40 minutes before the meeting begins.

Exercises¶

Programming¶

The expectations in this appendix are integrals that Sympy can evaluate symbolically. Here is the expected maximum and minimum of two uniform values, using the pdf of the maximum and the survival function of the minimum:

import sympy as sym

x = sym.Symbol("x", positive=True)

expected_max = sym.integrate(x * 2 * x, (x, 0, 1))
expected_min = sym.integrate((1 - x) ** 2, (x, 0, 1))
expected_max, expected_min

The general formula for the $k$-th order statistic of $N$ uniform values can be checked in the same way:

N, k = sym.symbols("N k", positive=True, integer=True)

pdf_k = N * sym.binomial(N - 1, k - 1) * x ** (k - 1) * (1 - x) ** (N - k)
expected_k = sym.simplify(sym.integrate(x * pdf_k, (x, 0, 1)))
expected_k

Numerical simulation gives an independent confirmation. Numpy’s sort sorts each sample, so column $k - 1$ of the sorted array holds the $k$-th order statistic:

import numpy as np

rng = np.random.default_rng(seed=0)
number_of_samples = 100_000
sample_size = 5

samples = rng.uniform(size=(number_of_samples, sample_size))
sorted_samples = np.sort(samples, axis=1)

for k in range(1, sample_size + 1):
    estimate = sorted_samples[:, k - 1].mean()
    exact = k / (sample_size + 1)
    print(f"k = {k}:  simulated {estimate:.4f},  exact {exact:.4f}")

k = 1:  simulated 0.1663,  exact 0.1667
k = 2:  simulated 0.3334,  exact 0.3333
k = 3:  simulated 0.5002,  exact 0.5000
k = 4:  simulated 0.6672,  exact 0.6667
k = 5:  simulated 0.8335,  exact 0.8333

Notable Research¶

The systematic study of order statistics grew out of early twentieth century work on extremes. Fisher and Tippett Fisher & Tippett, 1928 characterised the possible limiting distributions of the maximum of a large sample, a result completed by Gnedenko Gnedenko, 1943; together these form the foundation of extreme value theory, which underpins modern models of floods, heatwaves, and financial risk.

Rényi Rényi, 1953 gave an elegant representation of the order statistics of an exponential sample as a sum of independent scaled exponentials. This representation remains a standard tool for deriving the joint behaviour of order statistics.

The standard modern references are the monograph of David and Nagaraja David & Nagaraja, 2003, which surveys the field, and the more introductory treatment of Arnold, Balakrishnan and Nagaraja Arnold et al., 2008.

In game theory, expected order statistics of uniform samples are exactly what is needed to compute expected revenue in auctions: the winner’s payment in a second-price auction is the second highest valuation. This connection goes back to Vickrey Vickrey, 1961, whose analysis of sealed bid auctions is discussed in the Auction Games chapter.

Conclusion¶

For independent values with a common cdf $F$, the maximum has cdf $F(x)^N$ and the minimum has survival function $(1 - F(x))^N$; expectations then follow by integrating the pdf, or the survival function directly. Table A6.1 collects the key facts for the uniform distribution on $[0, 1]$.

Solutions¶