Reservoir Sampling

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.

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">{{hint}}</p>
<div class="reservoir">
  <span class="lbl">{{lbl_reservoir}}</span>
  <span id="held" class="held">—</span>
  <span class="lbl">{{lbl_next}}</span>
  <span id="next" class="next">1</span>
</div>
<div class="bars" id="bars"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="one" type="button">{{btn_one}}</button>
  <button id="many" type="button">{{btn_many}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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)$ time for n items, but only $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)$ 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.

"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.

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.