Reservoir Sampling

Concept Overview

Reservoir Sampling refers to a family of randomized algorithms used to select a random sample of size k from a population of unknown size n, typically represented as a data stream. The algorithm operates in a single pass over the data, requiring only O(k) memory, maintaining a fair sample of each finite prefix. An infinite stream never has a final uniformly sampled population.

Mathematical Definition

The fundamental property of a fair reservoir sampling algorithm is that after n items have been processed (where n ≥ k), every element from the stream has an equal inclusion probability of k / n.

P(Item i is in reservoir) = k / n, for all 1 ≤ i ≤ n

Key Concepts

Algorithm R: The most widely known algorithm in this family, attributed to Alan Waterman. It fills the reservoir with the first k elements. For each subsequent element at position i (where i > k, counting items from 1), it draws an integer juniformly from 0, …, i − 1. If j < k, reservoir slot jis replaced; otherwise the incoming item is discarded. Slots are zero-based, matching the visualization.
Inductive Proof of Correctness: We can prove the inclusion probability using mathematical induction. Base case: After exactly k items, all items are in the reservoir with probability 1 (which equals k / k). Inductive step: Assume after n - 1 items, the probability is k / (n - 1). When the n-th item arrives, it is selected with probability k / n. The probability that an item already in the reservoir is not replaced is the probability that the new item is rejected (1 - k/n), plus the probability that the new item is accepted but replaces a different slot ((k/n) · (k-1)/k = (k-1)/n). The sum is (n-k)/n + (k-1)/n = (n-1)/n. Therefore, the new inclusion probability for existing items is [k / (n - 1)] · [(n - 1) / n] = k / n.

Worked Example

Consider a reservoir size of k = 3 and a stream of length n = 12. We trace the inclusion probability calculation which yields a uniform 0.25 chance of selection.

Arriving item	Draw j	Decision	Reservoir afterward
1–3	None	Fill	1, 2, 3
4	2	Replace slot 2	1, 2, 4
5	2	Replace slot 2	1, 2, 5
6	5	Discard	1, 2, 5
8	1	Replace slot 1	1, 8, 5
10	2	Replace slot 2	1, 8, 10
12	10	Discard	1, 8, 10

This is the module’s fixed seed-42 trace; omitted items 7, 9 and 11 are discarded. The realized sample is one outcome. Across ideal random runs, each of the twelve items has inclusion probability3/12 = 0.25, including items absent from this particular sample.

For k=1, n=3, the draw for item 2 has two possibilities and the draw for item 3 has three. Of these six equally likely pairs, two end with item 1, two with item 2, and two with item 3. Thus each has probability 2/6 = 1/3.

Experiment

Experience the random decisions of the algorithm by using the Reservoir Sampling module.

Set "Reservoir size" to 3 and "Stream length" to 12.
Click "Reset seed", then "Step" three times. The sample is 1, 2, 3 and the visible inclusion probability is 1.000.
Click "Step" once more. The draw is 2, slot 2 becomes item 4, and the displayed probability becomes 3/4 = 0.750.
Continue until twelve items are processed. Read sample 1, 8, 10 and probability 0.250. Click "Reset seed" and repeat: the same seed gives the same sample. Changing either range resets the prefix too.
Try capacity 5 and length 4: every item is retained. Before the first Step, inclusion is shown as undefined. At the end, another Step leaves the state unchanged.

Limitations

The probability claim assumes independent uniform integer draws and samples stream positions, not distinct values or weighted records. A real implementation of Algorithm R takes O(n) time and O(k) storage, drawing only after the initial fill. This teaching interface replays a bounded prefix of at most 50 items to make Step and Reset reproducible; it is not a throughput benchmark. The fixed pseudo-random seed demonstrates decisions rather than proving fairness or providing cryptographic randomness. Vitter’s Algorithm Z reduces expected sampling CPU work to O(k(1 + log(n/k))) under the paper’s skip-access model; reading every record of a non-skippable live stream still incurs its input cost.

Historical Context

The fundamental algorithms were popularized by Donald Knuth in The Art of Computer Programming (Vol. 2), crediting Alan Waterman for Algorithm R. Jeffrey Vitter later expanded upon this with more efficient algorithms (X, Y, Z) in his 1985 paper, which optimized the process of skipping elements.

Real-world Applications

Log Processing: Selecting a representative sample of web requests or system logs for analysis without storing the entire massive log file.
Database Query Sampling: Databases returning a random sample of rows from a very large query result where the total count is initially unknown.
Machine Learning: Creating manageable mini-batches or training sets from infinite data streams in online learning scenarios.

Related Concepts

Monte Carlo Methods — Rely on random sampling to obtain numerical results.
Streaming Algorithms — General class of algorithms operating with limited memory on data streams.

References

These sources support the mathematical proof and time complexity discussed above.

Vitter, Jeffrey S. "Random sampling with a reservoir." ACM Transactions on Mathematical Software (TOMS) 11.1 (1985): 37-57. https://www.cs.umd.edu/~samir/498/vitter.pdf

Reservoir Sampling