🪣 Reservoir Sampling
Fair samples from a stream
Item 0 / 30
Expected inclusion: k/N
Setup
Controls
Stats
Target k/N
0.167
Runs
0
Max dev.
—
Status
Ready
Info & Theory

Reservoir sampling picks k items uniformly at random from a stream whose length N you do not know in advance, using only one pass and O(k) memory.

Algorithm R

  • Put the first k items into the reservoir.
  • For each later item i > k, pick a random integer j in 1…i. If j ≤ k, replace slot j with item i; otherwise discard it.

So item i enters the reservoir with probability exactly k/i.

Why it is uniform

Item i survives to the end if it is chosen on step i (prob k/i) and is then never evicted. The probability of not being evicted on a later step m is 1 − 1/m. Multiplying gives

(k/i) · ∏(m=i+1..N) (1 − 1/m) = (k/i)·(i/N) = k/N

so every element ends up in the sample with the same probability k/N. The histogram on the right is the empirical inclusion rate per item over many runs — it converges to the flat dashed line at k/N.

About this simulation

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

This simulation runs Algorithm R, the classic one-pass reservoir sampling method for picking k uniform random items from a stream of length N without knowing N in advance. Item i (1-indexed) is placed directly into the reservoir if i ≤ k; otherwise a random integer j in 1..i is drawn, and the item replaces reservoir slot j only if j ≤ k. The histogram at the bottom accumulates results over thousands of independent runs to empirically confirm that every item ends up in the final reservoir with the exact same probability k/N.

🔬 What it shows

A single streaming pass through N items (5–60) filling a reservoir of k slots (1–12), with the currently processed item highlighted and a live message showing whether it filled an empty slot, replaced an existing one, or was discarded. Below that, a growing histogram plots each item's empirical inclusion frequency across many completed runs against the theoretical target line k/N, along with the maximum observed deviation from that target.

🎮 How to use

Set Stream length N and Reservoir size k with the sliders, then press Play to animate Algorithm R item by item, or Step to advance one item at a time. Use Run 5000× to silently execute 5000 full passes and watch the histogram bars flatten out toward the dashed k/N target line, confirming the uniform inclusion guarantee empirically rather than just by formula. Reset clears all accumulated statistics and starts a fresh run.

💡 Did you know?

Algorithm R was popularised by Donald Knuth's The Art of Computer Programming and is still the standard technique for uniformly sampling from data streams too large to fit in memory — such as sampling log lines from a live server without storing the entire log. Its correctness comes from a beautifully simple probability argument: multiplying the chance an item is selected on its own turn (k/i) by the chance it survives every later eviction attempt collapses telescopically to exactly k/N.

Frequently asked questions

How does Algorithm R decide whether to keep or discard each item?

For the first k items (i ≤ k), the item goes straight into reservoir slot i−1 with certainty. For every later item i, the code draws a uniformly random integer j between 1 and i inclusive; if j ≤ k, the item replaces whatever was in slot j−1, and otherwise it is discarded entirely. This means item i is kept with probability exactly k/i and, if kept, evicts a uniformly random existing slot.

Why does this simple rule give every item the same overall probability k/N?

Item i survives to the final reservoir only if it is selected on its own turn (probability k/i) and then never evicted on any subsequent turn m > i, where the chance of not being evicted each time is 1 − 1/m. Multiplying k/i by the product of (1 − 1/m) for m from i+1 to N telescopes down to exactly (k/i)·(i/N) = k/N — identical for every item regardless of when it streamed past, which is exactly what the simulation's own histogram is built to demonstrate.

What does the "Run 5000×" button actually do differently from Play?

Play and Step animate a single pass through the stream with visual highlighting of the current item and reservoir slot, useful for following the mechanics of Algorithm R. Run 5000× instead calls a silent, unanimated version of the same algorithm 5000 times in a tight loop, tallying which item ended up in the reservoir after each full run, so the histogram accumulates enough samples to make the empirical inclusion frequency visibly converge on the theoretical k/N line.

What do the "Max dev." and histogram bars actually represent?

Each histogram bar shows, for one specific item index, the fraction of completed runs in which that item ended up somewhere in the final reservoir — literally counts[i] divided by the total number of runs. Max dev. is the largest absolute difference between any single item's observed inclusion frequency and the theoretical target k/N; as the number of runs grows, this maximum deviation should shrink toward zero, visually confirming the algorithm's uniformity guarantee.

Why is reservoir sampling useful when you cannot store the whole stream?

The whole point of Algorithm R is that it only ever needs to hold k items in memory (the reservoir itself) plus a running item counter, regardless of how long the stream N turns out to be — it does not need to know N in advance and never stores previously-seen items it has discarded. This makes it the standard choice for uniformly sampling from data sources like server logs, network traffic, or any dataset too large or too continuous to load into memory all at once.