Reservoir sampling

A uniform random sample of a stream of UNKNOWN length. One pass, O(k) memory, seen once.

The rule

• Keep the first k items in a reservoir
• For the i-th item: keep with probability k/i
• If kept, it replaces a uniformly random held item
• Needs neither the length nor the full data

Watch the reservoir

k=3 over A…J. Accept prob k/i shrinks: 3/4, 3/5, 3/6, … Accepted (green) replaces a random slot; rejected (red) → unchanged.

Uniform where others are biased

Reservoir: flat at k/n (spread 0.011). Keep-first-k: step (spread 1.0). Constant-½: skews late (0.43).

Why k/i is exact, not a heuristic

• Item survives item i with prob (i−1)/i → telescoping product
• Early item: ∏(i−1)/i = k/n. Late item j: (k/j)·(j/n) = k/n
• The k/i is the UNIQUE probability that telescopes to k/n
• Change it → the product stops cancelling → bias

Takeaway — and the book

The right idea makes the impossible routine: a probability instead of a guarantee. Fair sampling of the unstorable, in five lines. 56 chapters: the right structure separates tractable from intractable. Done.