Reservoir Sampling

Suppose a tick feed is firing prices at you all day and, at market close, you want a single tick chosen uniformly at random from everything that arrived — but you don't know in advance how many ticks there will be, and you can't afford to store all of them just to pick one later. Reservoir sampling solves exactly this: pick a random sample from a stream of unknown, possibly huge, length, using memory proportional only to the sample size.

The one-item case

Start with $k = 1$. Keep the first item as your current pick. When the second item arrives, replace your pick with it with probability $1/2$ — a coin flip. When the third item arrives, replace with probability $1/3$. In general, when item $i$ arrives, replace with probability $1/i$.

Why does this end up uniform? By induction: assume after $i$ items, each has probability $1/i$ of being the current pick. Item $i+1$ becomes the pick with probability $1/(i+1)$ — correct for it. An already-picked item survives only if not replaced, probability $i/(i+1)$, so its chance after this step is $\frac{1}{i} \times \frac{i}{i+1} = \frac{1}{i+1}$ — still uniform. The algorithm never needs to know how many items are left to come.

Worked example

A stream delivers ticks $A, B, C, D$ in order, and we sample $k=1$.

1. $A$ arrives: pick $= A$.
2. $B$ arrives (item 2): replace with probability $1/2$. Say the coin says yes: pick $= B$.
3. $C$ arrives (item 3): replace with probability $1/3$. Say no: pick stays $B$.
4. $D$ arrives (item 4): replace with probability $1/4$. Say no: pick stays $B$.

Run this process many times over the same stream and count how often each letter ends up chosen — it converges to 25% each, exactly uniform, even though $B$ "survived" two rejection rounds it happened to win.

Drag the parameters above and watch how a binomial with $p = 1/n$ mirrors the chance any single stream position ends up as the kept sample — the mechanism behind why the replace-with-probability-$1/i$ rule produces a flat, uniform outcome across positions.

Extending to k items

For a sample of size $k > 1$, keep the first $k$ items as the initial reservoir. For each subsequent item $i > k$, generate a random integer $j$ between 1 and $i$. If $j \le k$, overwrite reservoir slot $j$ with the new item; otherwise discard it. The same inductive argument holds slot by slot, and the whole scan costs $O(n)$ time and only $O(k)$ memory — you never allocate space for the full stream.

What this means in practice

Reservoir sampling shows up whenever a quant needs a random subset from something too large or too live to store: sampling log lines from a production trading system for a monitoring dashboard, drawing a random validation subset from a data pipeline that streams rows rather than loading a full table, or picking a random backtest window from years of tick data without holding it all in RAM. It is also a favorite coding-interview question precisely because the "obvious" answer — store everything, then sample — fails the moment the interviewer says "the stream doesn't fit in memory."