Reservoir

Can you take a fair sample from a stream when you do not know how long the stream is, and are only allowed to remember k items?

Algorithm R. The first k items fill the reservoir. Item i > k replaces a uniformly-chosen slot with probability k/i. The experiment runs the full stream many times and counts how often each index survives.

Change the stream length and the reservoir size. The bars show measured selection frequency per index; the line shows the theoretical k/n. They should sit on top of each other — and the residual you see is the honest cost of a finite number of trials.

Reports the maximum absolute deviation between measured frequency and k/n across all indices, over the trials actually run.

The figure shown under the canvas is computed by the run above, in this tab, from the settings currently selected. Change a control and it is recomputed. Nothing on this page is a stored or illustrative value.