Fair to Things You Have Forgotten
Pick six items uniformly from a stream of unknown length while holding only six. The items you threw away had exactly the same chance as the one in your hand.
What it is
Top strip: a stream of sixty items being walked, with the six currently held shown in green and the acceptance probability falling as the stream goes on.
Below: how often each position ends up selected, over tens of thousands of runs, for three policies. One of them is flat. The other two look reasonable and aren’t.
How it works
Algorithm R. Fill the reservoir with the first k, then for item i, keep it with probability k/(i+1), evicting a uniformly chosen resident to make room.
The proof that this is uniform is a short induction. The claim is the strange part. An item you saw at position 3 and evicted at position 8 has the same probability of being in the final sample as the item arriving right now. Not approximately. And you never need to know how long the stream is.
What surprised me
Not the uniformity, that’s the advertised feature. Two other things.
The wrong policies fail spectacularly, not subtly. 200,000 runs, sixty items, keeping six, ideal rate 10%:
| policy | first item | last item | worst deviation |
|---|---|---|---|
| keep with probability k/(i+1) | 9.93% | 9.90% | 1.6% |
| keep with probability ½ | 0.91% | 50.08% | 401% |
| always keep the newest | 0.01% | 100.00% | 900% |
A fixed probability of one half sounds like a reasonable approximation of “sample the stream”. It gives the last item a fifty-five times better chance than the first.
The 1/(i+1) schedule isn’t a refinement of the naive approach, it’s the only thing that works at all, and the falling probability is the entire mechanism. The reservoir has to get harder to enter at exactly the rate the stream grows.
It barely writes anything. The expected number of times an incoming item displaces a resident is k(H_n − H_k) ≈ k·ln(n/k):
| stream length | expected writes (k=10) | measured |
|---|---|---|
| 1,000 | 45.6 | 45.3 |
| 10,000 | 68.6 | 66.9 |
| 100,000 | 91.6 | 91.4 |
| 1,000,000 | 114.6 | not run |
Ten items sampled uniformly from a million, and the reservoir gets written to 115 times. Multiply the stream by ten and you add twenty-three writes.
So the cost is one comparison per item and basically nothing else. Almost all of the work is deciding not to do anything, which is a nice thing for an algorithm to be mostly made of.
What I would do next
Algorithm L, which skips ahead by drawing the gap to the next acceptance from a geometric distribution instead of testing every item. It should turn those n comparisons into about 115 of them with identical sampling.