Reservoir sampling: a uniform sample from a stream of unknown length

Goal

Select k items uniformly at random from a sequence whose length is unknown until it ends, in a single pass and with memory independent of the length: sampling log lines for inspection, picking rows from a large export, or choosing examples for a report without loading everything.

Prerequisites

A pseudo-random generator with a uniform integer function. Python's random module, documented as based on the Mersenne Twister, is adequate for statistical sampling; the same documentation warns that it is not for security purposes, so use secrets when an adversary must not predict the sample. The stream is read once; k items fit in memory.

Steps

1. Store the first k items in a list, the reservoir.
2. For every later item, numbered i (counting from 1), draw an integer j uniformly from 1 to i. If j is at most k, overwrite reservoir slot j with the item; otherwise discard the item.
3. When the stream ends, the reservoir is the sample. Its slot order carries no meaning; shuffle it if order matters downstream.
4. Convince yourself it is uniform. Item i enters with probability k/i. A reservoir item survives the arrival of item t with probability 1 - 1/t = (t-1)/t. Multiplying survival for t from i+1 to n telescopes to i/n, and (k/i) * (i/n) = k/n, the same for every item, including the first k, which enter with probability 1 and survive with probability k/n.
5. Special case k = 1: replace the single slot with probability 1/i.
6. Test with a small stream, for example 10 items and k = 3, by repeating the procedure many times and checking that each item's inclusion frequency approaches 0.3; also test that the code never asks for the length.
7. Seed the generator in tests for reproducibility and log the seed in production so that a reported sample can be regenerated.

Expected result

Every item is in the sample with probability exactly k/n, one random draw per item, memory proportional to k, and the stream length is never needed.

Limits and test basis

The sample is uniform over items, not over time or bytes; a bursty stream is sampled by count. Several parallel streams need their reservoirs merged with weights proportional to their item counts. Weighted variants and variants that skip ahead to save random draws exist and are not covered here. Correctness follows from the arithmetic in step 4; no measurements are claimed.