Reservoir Sampling

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.

Experiment

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

1. Set "Reservoir size" to 3 and "Stream length" to 12.
2. Click "Reset seed", then "Step" three times. The sample is 1, 2, 3 and the visible inclusion probability is 1.000.
3. Click "Step" once more. The draw is 2, slot 2 becomes item 4, and the displayed probability becomes 3/4 = 0.750.
4. 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.
5. 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.