Reservoir Sampling: Fair Samples from a Stream

Sampling when you do not know n

Picking k uniform random items from an array of known length n is easy - shuffle indices, take the first k. The harder problem is a stream: items arrive one at a time, you cannot go back, and you often do not know how many there will be in total. You still want, at any point the stream might stop, a set of k items where every item seen so far had exactly the same probability of ending up in your sample. That is what reservoir sampling guarantees, using only O(k) memory no matter how long the stream runs.

Algorithm R

Jeffrey Vitter's Algorithm R (1985) is disarmingly simple. Fill a reservoir of size k with the first k items outright. For every item after that, at position i, generate a uniform random integer j between 1 and i. If j is at most k, overwrite reservoir slot j with the new item; otherwise discard the new item and keep going. Every later item is considered exactly once, given a fair k/i chance of entering the reservoir, and if it does, it evicts a uniformly random existing slot.

const reservoir = [];
let i = 0;
for (const item of stream) {
  i++;
  if (reservoir.length < k) {
    reservoir.push(item);                 // fill the first k slots outright
  } else {
    const j = randomInt(1, i);            // uniform in [1, i]
    if (j <= k) reservoir[j - 1] = item;  // replace with probability k/i
  }
}

Why every item ends up equally likely

The proof is a clean induction. After processing the first k items, every one of them is in the reservoir with probability exactly 1, which is trivially uniform. Assume that after processing i minus 1 items, every one of them has probability k over (i minus 1) of currently occupying a reservoir slot. Item i is admitted with probability k over i by construction. For an earlier item to survive this step, either item i is rejected, which happens with probability 1 minus k over i, or item i is admitted but does not evict that particular slot, which happens with probability (k over i) times (k minus 1 over k). Multiplying through and simplifying recovers exactly k over i for every one of the i items - so the invariant holds at every single step, not just at the end.

Weighted and faster variants

Algorithm R draws one random number per item, which is wasteful when items are mostly rejected on a very long stream. Algorithm L and related skip-ahead methods compute, in closed form, how many items will be skipped before the next admission, jumping straight to the next relevant index instead of rolling a die for every item. When items carry unequal importance weights, the unweighted guarantee no longer applies; weighted reservoir sampling (Efraimidis and Spirakis, A-ExpJ) assigns each item a key derived from a random number raised to the power of one over its weight, and keeps the k items with the largest keys, which samples proportionally to weight while remaining a single streaming pass.

Frequently asked questions

Try it live

Everything above runs in your browser - open Reservoir Sampling and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.