Articles
Order Statistics Interview Questions: Maxima, Minima, and Sample Size
Derive expected sample maxima and minima, calculate how sample size changes threshold probabilities, and avoid continuous-versus-discrete traps.
“You draw five independent values uniformly from zero to one. What is the expected maximum, and what changes if you draw ten?” The answer is not “the maximum is one.” One is the upper endpoint; every finite continuous sample is below it with probability one. The useful interview move is to derive the maximum’s distribution from a simple event, then compute an expectation or a threshold probability. For five draws, the expected maximum is 5/6; for ten, it is 10/11, under the stated independent Uniform(0,1) model.
This guide derives maxima and minima, changes the sample size, and checks a discrete-die variant. Evidence boundary: Berkeley’s probability lecture notes establish the order-statistic identities. The worked values, sample-size decision, and simulation below are editorial exercises.
Ask what is random before taking an extreme
Let X1, ..., Xn be independent observations with the same cumulative distribution function F(x) = P(Xi <= x). Sort their realized values as X(1) <= ... <= X(n). The minimum is X(1), and the maximum is X(n). These are random variables across repeated samples. “Order statistic” here means a distribution of sorted random observations; it is different from a data-structure task such as finding the k-th item in a mutable multiset.
State the independence and common-distribution assumptions. If the observations have different CDFs but remain independent, products of their individual CDFs still work. If they are dependent, multiplying marginal probabilities usually fails. For example, if all ten reported values are exact copies of one draw, their maximum has the same distribution as one draw, not the distribution of ten independent draws. This is why saying “ten samples” without describing their generation can be misleading.
The CDF route avoids an early integration mistake. The event max(X1,...,Xn) <= x occurs exactly when every observation is at most x. Independence gives Fmax(x) = [F(x)]^n. The event min(X1,...,Xn) > x occurs when every observation exceeds x, so Fmin(x) = 1 - [1-F(x)]^n. These formulas apply to discrete distributions as CDF statements too; a density exists only where differentiability assumptions justify one.
Derive the uniform answer, not just memorize it
For Xi ~ Uniform(0,1), F(x)=x on [0,1]. Thus Fmax(x)=x^n and Fmin(x)=1-(1-x)^n on that interval. Differentiating gives fmax(x)=n*x^(n-1) and fmin(x)=n*(1-x)^(n-1). The maximum density concentrates near one as n grows; the minimum density concentrates near zero. The mirror symmetry is a useful sanity check because replacing each draw Xi with 1-Xi swaps minimum and maximum.
Integrate x*fmax(x) from zero to one to obtain E[max]=n/(n+1). The mirrored result is E[min]=1/(n+1). For n=1, both are 1/2; for n=4, they are 4/5 and 1/5. The gap between expected extremes is (n-1)/(n+1). It grows toward one, but the expected maximum never equals one for finite n.
| Independent uniform draws | Expected minimum | Expected maximum | P(max > 0.9) |
|---|---|---|---|
| 1 | 0.5000 | 0.5000 | 0.1000 |
| 2 | 0.3333 | 0.6667 | 0.1900 |
| 5 | 0.1667 | 0.8333 | 0.4095 |
| 10 | 0.0909 | 0.9091 | 0.6513 |
The last column comes from 1-0.9^n, not from the expected value. That distinction matters in interviews. An expected maximum above 0.9 does not mean the maximum exceeds 0.9 with probability one. For ten draws, expectation is about 0.9091, while the chance of at least one value above 0.9 is about 0.6513.
Turn a probability target into a sample size
Suppose the interviewer asks, “How many independent uniform draws are needed so the chance of observing at least one value above 0.95 is at least 90%?” The complement is easier: P(max <= 0.95)=0.95^n. Require 1-0.95^n >= 0.90, or 0.95^n <= 0.10. Both logarithms are negative, so dividing reverses the inequality: n >= log(0.10)/log(0.95), approximately 44.89. The smallest integer is 45.
Check the boundary rather than trusting a rounded logarithm: 1-0.95^44 is below 0.90, and 1-0.95^45 is above 0.90. The model assumes independent, identically distributed uniform values and an exact strict threshold. In a continuous model, > and >= at one point have equal probabilities. That shortcut does not carry over to a discrete distribution with positive mass at the threshold.
A related question asks for the median, not the mean, of the maximum. Solve m^n=0.5, giving m=0.5^(1/n). The 90th percentile solves q^n=0.9. Do not substitute n/(n+1) into a percentile question. Mean and quantile are different summaries of the same distribution. If the sample has a nonuniform CDF F, solve [F(q)]^n=p, or F(q)=p^(1/n); an inverse CDF may then provide q if it exists in the usual sense.
Minimums, kth values, and the counting view
For the minimum, the survival event often reads more naturally than the CDF. P(min > x)=[1-F(x)]^n, so for uniform draws P(min <= 0.1)=1-0.9^n. This is numerically the same chance that the maximum exceeds 0.9, by symmetry. If an answer accidentally gives 0.9^n for “at least one draw below 0.1,” it has confused the complement with the requested event.
The kth-smallest value needs one more counting step. X(k) <= x exactly when at least k of the n observations are at most x. Under independent identical draws, the count is binomial with success probability F(x), so P(X(k) <= x) = sum_{j=k}^n C(n,j) F(x)^j [1-F(x)]^(n-j). For uniforms, X(k) has a Beta(k, n-k+1) distribution and expectation k/(n+1). Berkeley’s notes derive the density; the counting event is the robust way to reconstruct it under interview pressure.
Be precise about indexing: k=1 is the minimum, k=n is the maximum. A prompt that says “third largest” maps to X(n-2), not X(3), unless the sample size happens to make them equal. Ties are harmless for the max/min CDF formulas, but a continuous-density derivation assumes tie probability zero. For discrete samples, use the binomial-count CDF directly and specify how ties are ranked if the interviewer asks for a particular ordered position.
The die-roll follow-up is discrete
For n independent fair six-sided rolls, P(max <= k)=(k/6)^n for integer k from one to six. The tail-sum formula for a positive integer random variable gives E[max] = sum_{k=1}^6 P(max >= k) = sum_{k=1}^6 [1-((k-1)/6)^n]. Similarly, P(min >= k)=((7-k)/6)^n, so E[min]=sum_{k=1}^6 ((7-k)/6)^n. For one roll, both formulas return 3.5. As n grows, the expected maximum approaches six and the expected minimum approaches one.
Do not differentiate the discrete CDF and pretend it has the continuous uniform density. It jumps at integer outcomes. If you need P(max = k), subtract neighboring CDF values: (k/6)^n - ((k-1)/6)^n. For P(min = k), subtract survival terms. The die question is a useful check of whether you understand the event argument rather than memorizing the continuous uniform result.
A small, reproducible simulation check
Simulation is an independent numerical check, not a proof of a symbolic formula. The code below uses a fixed seed, separate samples for each trial, and records both the average maximum and the event frequency.
from random import Random
def check_maximum(n=5, trials=100_000, seed=23):
rng = Random(seed)
maxima = [max(rng.random() for _ in range(n))
for _ in range(trials)]
return sum(maxima) / trials, sum(m > 0.9 for m in maxima) / trials
print(check_maximum())
For n=5, compare the first output with 5/6 and the second with 1-0.9^5 = 0.40951. Monte Carlo estimates vary around those values; do not report a single run as an exact equality. If the estimate is far away, check whether the inner draw generator was accidentally reused as one value across the trial, whether n was counted correctly, and whether the requested event used > or <=. For a quick interview explanation, the analytic event argument is enough; the simulation is valuable when you want to test code or intuition.
A sample maximum is also a biased estimator of the upper endpoint theta of Uniform(0,theta): its expectation is n*theta/(n+1). Multiplying the observed maximum by (n+1)/n removes that bias under this exact model, although unbiasedness alone does not prove it is the best estimator under every criterion. If the sampling distribution is unknown, you cannot infer an endpoint from one maximum by simply applying the uniform correction. This follow-up tests whether the model assumptions travel with the formula.
Fast interview answers and traps
Why raise the CDF to n? All n independent observations must fall below x for their maximum to do so. Identical distributions make every factor F(x); independence makes the product valid.
Why is the minimum a complement? It is easier to describe all observations being above x; subtract that event’s probability from one.
Does a larger sample always give a larger observed maximum? For nested samples—keep the first n and add another draw—the maximum cannot decrease. For two independently generated sample sets, a ten-draw maximum can happen to be smaller than a five-draw maximum. Distinguish monotone coupling from a comparison of random realizations.
What if observations are correlated? Replace the product with a joint probability. Positive dependence can make the gain from more observations much smaller. Ask for the dependence structure before applying the iid formula.
What if values repeat? The max/min CDF event still works for iid discrete observations. Densities and zero-probability tie arguments do not. Specify the rank convention if a middle order statistic is requested.
Why is this not Fenwick-tree order statistics? A Fenwick tree can locate a rank in a dynamic frequency multiset. Here the unknown is a probability distribution of sample extremes; the calculation starts from the sampling model, not a maintained data structure.