Algorithms · Streaming

The Fair Draw.

Elements are streaming past — a giant log file, a live feed, a database cursor you can’t rewind. You must pick one uniformly at random, but you don’t know how many will come and can’t store them all. The trick holds a single slot and a shrinking coin: keep the i-th arrival with probability 1/i. When the stream ends, everyone had an equal shot.

O(n) time · O(1) space · one pass · streaming
stream

Elements arriving one at a time, count unknown, no going back.

reservoir

The one slot you hold — the current pick.

1/i rule

The i-th element replaces the pick with probability 1/i.

uniform

At the end, every element seen is equally likely to be held.

reservoir.js — one slot, a shrinking coin
Ready
A stream of elements arrives one by one. We hold a single reservoir slot. Press Next: the i-th element flips a coin that lands "keep" with probability 1/i — and if it does, it takes the slot.
0
arrived i
keep prob 1/i
held

How it works

The elegance is that fairness is maintained at every step, not fixed up at the end. The rule looks arbitrary — why 1/i? — but it exactly balances two forces: a new element deserves its fair share now, and every old element must have its share diluted by exactly the right amount to stay equal.

1

First element: always keep

With one element, it’s trivially the pick — keep with probability 1/1 = 1.

2

i-th element: keep with 1/i

Flip a coin weighted 1/i. Heads → it replaces the current pick. Tails → the pick stays.

3

The balance holds

After i elements, each is held with probability exactly 1/i. The new one gets 1/(i+1); each old one keeps its share × the reject chance i/(i+1) — also 1/(i+1).

Stop anytime — still fair

Because it’s balanced every step, you can end the stream at any point and the held element is a uniform pick from all seen so far.

Time
O(n)
Space
O(1)
Passes
1
Needs length?
No

The code

# pick one element uniformly from a stream, O(1) space def reservoir_sample(stream): pick = None for i, x in enumerate(stream, start=1): if random.random() < 1 / i: # keep the i-th with prob 1/i pick = x return pick # sample k elements: fill first k, then keep i-th with prob k/i, # replacing a random slot. One pass, O(k) memory.

No length needed, no second pass, no storing the input — which is exactly why it works on infinite or unmeasurable streams where you literally cannot do "pick a random index from 0..n-1".

Quick check

1. Why keep the i-th element with probability exactly 1/i?

2. What’s the killer advantage over "pick a random index"?

FAQ

What is reservoir sampling?

A one-pass method to draw a uniform random sample from a stream of unknown or huge length, storing only the sample. For one element: keep the i-th arrival with probability 1/i.

Where is it used?

Random line from a giant file, sampling live logs or click streams, random records from a database cursor, unbiased telemetry sampling — anywhere you can’t store or count the input first.

How do I sample k elements?

Keep the first k, then for each later i-th element keep it with probability k/i, replacing a random one of the k slots. Still one pass, O(k) memory, uniform subset.

Can I do weighted sampling?

Yes — the A-Res / A-ExpJ algorithms extend reservoir sampling to weights, so elements are sampled proportional to weight in one pass. The unweighted 1/i rule is the special case where all weights are equal.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms