Reservoir Sampling — Algorithm R

A stream flows in one item at a time. Fill k slots, then keep the i-th item with probability k/i, evicting a uniformly random slot. When the stream ends, each item has probability k/n of being in the reservoir.

step 0

Stream & Reservoir

Incoming stream (current item highlighted):
Reservoir — k slots:
Replace probability for item i: —
Green/blue bar = keep probability k/i. The red tick is where the random draw landed (left of the bar boundary → keep).
verdict: press Step to begin
seen i = 0 kept = 0 discarded = 0 RNG draws = 0
fill phase current item kept discarded

Complexity

OperationTimeSpace
Process one itemO(1)—
Whole stream (Algo R)O(n)O(k)
RNG calls (Algo R)O(n)—
RNG calls (Algo L)O(k·log(n/k))O(k)
Naive shuffleO(n)O(n)

Operation Log

Press Step to advance one item. The first k items fill the reservoir; each later item is kept with probability k/i and evicts a random slot if kept.
Self-contained visualization. Each "keep with probability k/i" decision uses one random draw; watch the gauge shrink as i grows — later items are kept less often, but they also have fewer chances to be evicted, so every item ends with probability k/n. See junior.md for the walkthrough and professional.md for the uniformity proof.