Introduction

Imagine items flying past you one at a time: tweets in a firehose, log lines from a server, cards being dealt face-up and then burned. You want to keep a fair random sample of, say, one item — every item that ever passes should have an equal chance of being the one you end up holding.

Easy, if you can store everything: collect the whole list, count it, then pick a random index. But here's the catch — you can only look at each item once, you can't store the stream, and you don't even know how long it is. It might stop after 10 items or after 10 billion.

That sounds impossible. How can every item be equally likely when you have to decide what to keep before you know how many items there are? The answer is a tiny, beautiful algorithm called reservoir sampling, and it gets the probabilities exactly right.

Try It

Below, items numbered 1, 2, 3, … stream past a reservoir that holds just k of them. The rule is almost suspiciously simple: when item number i arrives, keep it with probability k / i, and if you keep it, drop one of the items already in the reservoir at random.

<p class="hint">A stream of items <b>1, 2, 3, …</b> flows past a reservoir of size <b>k = 1</b>. When item <b>i</b> arrives it is kept with probability <b>k/i</b>; if kept, it evicts a random item already inside. Stream items, or run thousands of full streams and watch every position get chosen <b>equally often</b>.</p>
<div class="reservoir">
  <span class="lbl">Reservoir (k=1):</span>
  <span id="held" class="held">—</span>
  <span class="lbl">next item:</span>
  <span id="next" class="next">1</span>
</div>
<div class="bars" id="bars"></div>
<div class="status" id="status">Stream items one by one, or run many trials.</div>
<div class="btns">
  <button id="one" type="button">Stream one</button>
  <button id="many" type="button">Run many trials</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.reservoir { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin: .4rem 0 .8rem; }
.lbl { font-size: .85rem; color: #555; }
.held, .next { width: 40px; height: 40px; display: inline-flex; align-items: center;
        justify-content: center; font: 700 16px ui-monospace, monospace; border-radius: 8px; }
.held { background: #1d3557; color: #fff; }
.next { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.bars { display: flex; align-items: flex-end; gap: 4px; height: 130px; margin: .6rem 0;
        border-bottom: 2px solid #ccc; padding-bottom: 2px; }
.col { flex: 1; display: flex; flex-direction: column; align-items: center; justify-content: flex-end; gap: 3px; }
.bar { width: 100%; background: #457b9d; border-radius: 4px 4px 0 0; transition: height .15s; min-height: 1px; }
.bar.lit { background: #e63946; }
.tag { font: 600 11px ui-monospace, monospace; color: #555; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #0a4d68; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Reservoir sampling, Algorithm R (Vitter, 1985), with reservoir size k = 1.
// Stream length here is N items. When item i (1-based) arrives, keep it with
// probability k/i; if kept, it replaces a random item in the reservoir.
// Claim: every position 1..N ends up the chosen one with probability k/N = 1/N.
const N = 8;          // items in one stream pass
const K = 1;          // reservoir size
let i = 0;            // items seen so far in the current live pass
let held = null;      // current reservoir contents (single item, since K=1)
const counts = new Array(N).fill(0); // how often each position is the survivor
let trials = 0;

// One streaming decision for the live, step-by-step view.
function step(){
  if (i >= N){ setStatus('Stream finished. Reset to replay, or run many trials.'); return; }
  i++;
  // keep item i with probability k/i
  if (Math.random() < K / i) held = i;
  render();
  if (i === N){ counts[held-1]++; trials++; setStatus(fmt('Survivor of this pass: item %held%.', { held: held })); }
  else setStatus(fmt('Item %i% arrived (kept with prob %K%/%i%).', { i: i, K: K }));
}

// Run one full stream silently and return the surviving position.
function onePass(){
  let h = null;
  for (let t = 1; t <= N; t++){ if (Math.random() < K / t) h = t; }
  return h;
}

function runMany(){
  for (let t = 0; t < 20000; t++){ counts[onePass()-1]++; trials++; }
  held = null; i = 0;
  render();
  const exp = (trials / N).toFixed(0);
  setStatus(fmt('%trials% trials. Each position expected ~%Number% times — see how level the bars are.', { trials: trials.toLocaleString(), Number: Number(exp).toLocaleString() }));
}

function render(){
  document.getElementById('held').textContent = held === null ? '—' : held;
  document.getElementById('next').textContent = i >= N ? '—' : (i + 1);
  const max = Math.max(1, ...counts);
  const bars = document.getElementById('bars'); bars.innerHTML = '';
  for (let p = 0; p < N; p++){
    const col = document.createElement('div'); col.className = 'col';
    const bar = document.createElement('div');
    bar.className = 'bar' + (held === p + 1 ? ' lit' : '');
    bar.style.height = (counts[p] / max * 110 + 1) + 'px';
    const tag = document.createElement('div'); tag.className = 'tag'; tag.textContent = p + 1;
    col.appendChild(bar); col.appendChild(tag); bars.appendChild(col);
  }
}
function setStatus(t){ document.getElementById('status').textContent = t; }
function reset(){ i = 0; held = null; render(); setStatus('Stream items one by one, or run many trials.'); }

document.getElementById('one').addEventListener('click', step);
document.getElementById('many').addEventListener('click', runMany);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

Press Stream one to feed items in one at a time, or Run many trials to repeat the whole stream thousands of times and tally how often each position survives. Notice the punchline: even though early items had many chances to be evicted, every position ends up in the final sample equally often. One pass, a fixed-size reservoir, and perfectly uniform odds.

The Real Complexity

What makes reservoir sampling remarkable is that it is solved, completely, with a short proof and tight resource bounds.

  • One pass, tiny memory. The classic method — Algorithm R, popularized by Jeffrey Vitter in 1985 — reads the stream once: O(n)O(n) time for n items, but only O(k)O(k) memory, independent of how long the stream is.
  • The rule. Fill the reservoir with the first k items. Then for each later item i (with i > k), keep it with probability k / i; if kept, it replaces a uniformly random item already inside.
  • Why it's uniform. Consider any item that arrived at position i. It enters the reservoir with probability k/i. To still be there at the end (after n items), it must survive every later step: at step j > i it is evicted only if a new item is kept (prob k/j) and it is the unlucky one chosen (prob 1/k). So it survives step j with probability 1 − 1/j = (j−1)/j. Multiply: (k/i) · (i/(i+1)) · ((i+1)/(i+2)) ⋯ ((n−1)/n). The chain telescopes to exactly k / n — the same for every item, no matter when it arrived.
  • Provably optimal in spirit. You can't do better than one pass when you can't revisit data, and you must hold at least k items to output k. Vitter's later variants (X, Y, Z) even cut the number of random numbers needed from O(n)O(n) to O(k log(n/k)).

That telescoping product is the whole magic trick: the shrinking acceptance probability k/i exactly cancels the growing risk of later eviction.

Where It Matters

"Keep a fair sample of a stream too big to store" is everywhere once you start looking:

  • Log and telemetry sampling. Servers emit millions of events; you keep a uniform sample for dashboards and debugging without buffering the firehose.
  • Big-data and databases. Query engines use reservoir sampling to estimate aggregates and to draw SAMPLE rows in a single scan over a table of unknown size.
  • Machine learning. Subsampling a massive or infinite training stream into a manageable, representative set is exactly this problem.
  • A/B testing and online systems. Picking a uniform slice of live traffic, or a random winner among an unknown number of entries, is reservoir sampling in disguise.

It also pairs naturally with other streaming ideas: where Bloom filters answer "have I seen this?" in tiny memory, reservoir sampling answers "give me a fair handful" — both squeezing a one-pass, bounded-memory guarantee out of an unbounded stream, a recurring theme in P vs NP-style resource questions.

Conclusion

Reservoir sampling is one of those rare problems that looks impossible and turns out to be completely solved. With nothing but a fixed-size reservoir and the rule keep item i with probability k/i, you draw a perfectly uniform sample from a stream you can only see once and whose length you never learn.

The proof fits on a napkin and the code fits in a tweet, yet the result powers everything from server dashboards to machine-learning pipelines. The next time data is rushing past faster than you can store it, remember: a fair sample is still within reach — you just have to let the probabilities telescope.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reservoir-sampling/Content licensed under CC BY-NC 4.0.