A Fair Sample in 100 Slots, Forever

After 10,000 log lines, every line can have exactly a 1% chance of occupying a 100-slot buffer. After a billion lines, the buffer still holds 100 and every line still has the same inclusion probability: one in ten million.

I find that result mildly absurd. The stream never tells you its final length, old items cannot be revisited, and memory never grows. Reservoir sampling still keeps a uniform sample without replacement.¹

The problem in one sentence

Items arrive one by one: $x_1, x_2, x_3, \dots$. You do not know how many there will be. After seeing $n \ge k$ items, you want exactly k of them in memory, with every item seen so far having probability

If you have seen 10,000 log lines and your reservoir size is 100, each line should have a 1% chance of being in memory right now. Not just the recent ones. Not just the lucky early ones. All of them.

The algorithm

The simplest version is often called Algorithm R.

1. Put the first k items directly into the reservoir.
2. When the $(t+1)$-st item arrives, keep it with probability $k / (t+1)$.
3. If you keep it, evict one of the current k reservoir items uniformly at random.

No history, no estimate of the final stream length, and no growing state.

export function reservoirSample<T>(
  stream: Iterable<T>,
  k: number
): T[] {
  if (!Number.isInteger(k) || k < 0) {
    throw new Error("Sample size must be a non-negative integer");
  }

  const reservoir: T[] = [];
  let seen = 0;

  for (const item of stream) {
    seen += 1;

    if (reservoir.length < k) {
      reservoir.push(item);
      continue;
    }

    const j = Math.floor(Math.random() * seen);

    if (j < k) {
      reservoir[j] = item;
    }
  }

  return reservoir;
}

The key line is const j = Math.floor(Math.random() * seen).

If j < k, the new item enters the reservoir. Otherwise it is ignored. That single line silently implements the “keep with probability $k$ / seen” step.

Why it works

The proof is a short induction.

Take the moment when you have seen $t$ items and your reservoir is already fair. Now item $t+1$ arrives. It should be included with probability $k/(t+1)$, and that is exactly what the algorithm does.

What about an older item already in the reservoir? It was there with probability $k/t$. Once the new item arrives, it survives unless two things happen: the new item is accepted (probability $k/(t+1)$), and this specific old item is chosen for eviction (probability $1/k$).

The probability of getting kicked out is

The survival probability is $t/(t+1)$, so the old item remains with probability

The old items and the new item all end up with the same inclusion probability.

Step through items one at a time above, or let it auto-play. Watch the reservoir fill up greedily at first, then become increasingly selective. Switch to the fairness view and run thousands of simulations; the inclusion histogram flattens until the invariant becomes visible.

The cost hidden by the proof

Algorithm R examines every item and generates a random integer for every item after the first k. That is optimal if the application must inspect each record anyway, but sampling itself can become the bottleneck when k is tiny and the stream is fast.

Vitter’s 1985 paper is remembered for faster reservoir algorithms that skip over runs of rejected records instead of flipping a fresh decision for each one. The simple version above remains the best explanation of the invariant. It is not the end of the performance story.

A reservoir is fair, not balanced

Reservoir sampling is not trying to make the buffer look aesthetically balanced, upweight rare classes, preserve recent items, or track concept drift. Its job is narrower: maintain a uniform sample without replacement from a stream of unknown length.

If your only goal is “give me a representative size-$k$ sample of an unknown-length stream,” that neutrality is exactly the point.

When fairness is not the right goal

In continual learning, observability, or product analytics, a buffer may not want to mirror the raw stream exactly. If the stream is highly imbalanced, bursty, or temporally correlated, a plain uniform reservoir preserves those distortions.

At that point you have changed the problem. You may want a recency window, a stratified sampler, a replay buffer that overrepresents rare classes, or a sampler that tracks a target distribution. Those are valid designs, but they are no longer the neutral guarantee above.

Classic reservoir sampling asks for fairness with respect to the stream. Many production buffers need usefulness with respect to a task. Confusing those two goals produces a perfectly fair buffer that answers the wrong question.