Experiment № 078 · The story
Fair Without Remembering
Why I picked it
Somebody once described reservoir sampling to me as a party trick, and I have never quite stopped being annoyed that it works. Here is the claim: a stream of items goes past you exactly once. You may not rewind it, you are not told how long it is, and you may hold on to only k of them at a time. When the stream ends — whenever that is — hand me a sample of size k in which every item that ever went past was equally likely to be chosen. That should be impossible. Uniformity feels like something you can only build once you know the size of the thing you are sampling from, and here the size is exactly what you are denied. The whole method fits in two lines: keep the first k; after that, keep item number i with probability k/i, and if you keep it, throw out one of your survivors at random. Vitter named it Algorithm R in 1985 and it was already folklore then. I have read the induction proof more than once and still not really believed it, so I built the thing that lets me check.
What I enjoy about it
The gate is the part worth watching. Early on it swallows almost everything; by item 500 it lets one in a hundred through, and the sector shrinks towards nothing while the stream keeps pouring past. It looks like a machine that is getting steadily less interested — and yet the histogram underneath comes out flat, because the two effects cancel exactly. An early item had a wonderful chance of getting in and then had to survive hundreds of chances to be evicted; a late item barely got in but had almost no time left to be thrown out. Neither advantage is free. The best way to feel that is to switch strategies. A fixed coin flip is the sensible-looking mistake: keep each arrival with probability 0.5 regardless of position. Run a few thousand and the histogram is a wall leaning hard to the right — an item near the end is dozens of times likelier to be in your sample than an item near the start, and nothing in the code announces that. Keep the first k is the same bias wearing an honest face; it is what "we looked at the first ten thousand rows" really means. Then click any bar to follow a single position across every run and watch its frequency creep towards k/n and stay there.
Something you might take away
Notice what the algorithm never touches: n. The stream length appears in the answer — every position ends up with probability exactly k/n — but it appears nowhere in the code, because the running count i is standing in for it the whole way. Fairness did not require knowing how big the population was; it required the acceptance rate to decay at exactly the right speed. That is worth stealing whenever you are sampling something that will not sit still to be counted: log lines, events, rows arriving from a query you cannot afford to buffer, an infinite feed. And it is worth remembering in the other direction too, as a smell test. Any time a sample was taken from a stream, ask what the keep-rate was as a function of position. If it did not fall off as the stream ran, the sample is not of the stream — it is of the end of the stream, and every conclusion drawn from it quietly means "lately".