Members of a crowd file past you one at a time. You may hold exactly one. You are never told how many will come, and once someone has passed you cannot call them back. When the last one goes by, the person in your hand must have had the same chance as everyone else. It sounds impossible. One rule does it.
Here is the honest shape of the problem. A file of items comes at you in order, and you get to see each one only as it passes. You have room for a single keeper. Crucially, you do not know the length of the line in advance, so you cannot say "I will keep the 47th" or roll a die over a count you do not have. When the stream finally stops, the item you are holding should be a uniformly random one, as if you had laid the whole crowd out and pointed blind.
The rule that achieves it, called Algorithm R, is almost too short to trust. Keep the first item. Then, when the i-th item arrives, let it knock out whoever you are holding with probability 1/i. The second arrival replaces the first half the time; the third takes over a third of the time; the hundredth barges in only once in a hundred. Try it. Step the stream one at a time and watch who survives, or let it run.
The surprise is that a rule whose odds visibly decay does not favor the early arrivals (who had many chances to be evicted) nor the late ones (who barely had a chance to enter). It is exactly flat. You can prove it in one line, and it is worth doing by hand because the cancellation is the whole magic.
Fix any position j. For item j to be the final survivor, two things must happen: it must take the slot when it arrives (probability 1/j), and then every later arrival must decline to evict it. Arrival i > j leaves it alone with probability 1 − 1/i = (i−1)/i. Multiply:
Every numerator cancels the next denominator. The j in front cancels the j that opens the product; the whole chain collapses to
No j left in the answer: the position dropped out. Whoever you are holding at the end had probability exactly 1/n, and the algorithm never once needed to know n while it ran. Below, run the whole thing many times over and watch the survivor counts settle onto the flat line 1/n. This is the proof made of tallies rather than algebra.
The 1/i schedule is not decoration. It is the only schedule that flattens. To feel why, try the rule almost everyone reaches for first: at each step, replace what you hold with some fixed probability p. It looks even-handed, symmetric, no favoritism. It is a disaster. The very last item wins whenever it chooses to replace, which is with probability p, no matter how long the line was. The second-to-last wins with probability p(1−p), and so on: the chances fall off geometrically from the end, so recent arrivals dominate and the front of the line is all but forgotten. Slide p and watch the skew; the reservoir's 1/i rule is drawn beside it for contrast.
The same idea scales. To keep a fair sample of k items instead of one, fill the reservoir with the first k arrivals; then, when item i > k comes, admit it with probability k/i, and if admitted let it replace one of the k held items chosen at random. The same telescoping argument now gives every item probability exactly k/n of being in the final sample, using memory for only k items however long the river runs.
And what if the items are not equal? Suppose each carries a weight, and you want heavier items to appear proportionally more often. Efraimidis and Spirakis found a rule as clean as the original (2006). Give item i a random key ui1/wi, where ui is uniform on (0,1) and wi is its weight; keep the item with the largest key. For a single keeper the guarantee is exact and beautiful: item i wins with probability wi / Σw. The proof is one integral. The key of item i lands below x with probability xwi, so the chance it beats all the others is
Set the four weights below and run: the empirical win-rates climb to wi/Σw. (Equal weights collapse it back to the plain uniform reservoir, as it must.)
This is not a museum piece. The moment a system must sample from something it cannot fit in memory or whose size it does not know until the end, reservoir sampling is the tool. Think of a firehose of log lines or telemetry events arriving faster than you can store them: to keep a uniform sample of, say, a thousand for later analysis, you run Algorithm R with k = 1000 and touch each event exactly once, holding a fixed thousand no matter whether a million or a billion go by. You have used it without knowing: the Unix tool shuf, asked for shuf -n 1000 lines of a file, switches to a reservoir once the input grows past a few megabytes, so it keeps just those thousand lines in memory instead of loading the whole file (this is right there in coreutils' shuf.c, with its comment on choosing "the fate of the next line, with decreasing probability"). The same one-pass, bounded-memory shape recurs across databases, big-data pipelines, and streaming frameworks whenever a representative subsample is wanted in a single pass.
Its lineage is old, and worth telling straight because the tidy single-inventor version is a myth. The single-item rule appears as Algorithm R in Knuth's The Art of Computer Programming, credited there to Alan Waterman, who by Knuth's own account never published it himself (it was later rediscovered independently, so there is no clean "first"). In 1985 Jeffrey Vitter popularized the name reservoir sampling and added a decisive speed-up. His method still reads every arrival, but instead of flipping a coin at each one it computes in a single draw how many arrivals to skip before the next replacement, cutting the number of random draws (and the CPU work) from proportional to n down to about k(1 + log(n/k)). The sample it produces is identical in distribution; only the labor changes. (Reservoir sampling is never sublinear in the stream: any correct method must see every item go by.)
The core claims here are theorems and are exact: the single-item rule gives every position probability 1/n (a telescoping product, computed in exact rationals in the verifier for n up to 100); the general rule gives every item k/n; the fixed-probability rule is provably geometric toward the end, not uniform; and the weighted single-keeper rule gives wi/Σw (an integral, checked three ways). Every histogram on this page is a live Monte-Carlo simulation with a fixed seed, and the same simulations run offline pass a chi-square uniformity test and match the exact formulas to within sampling error.
Two honest edges. First, a histogram converging toward flat is evidence of uniformity, not the proof of it; the proof is the algebra above, and the tallies are there so you can watch the theorem hold rather than take it on faith. Second, the weighted rule's clean wi/Σw statement is for a single survivor. Taking a weighted sample of several items at once with this key method (A-Res) draws them without replacement, item by item in proportion to remaining weight; the marginal probability that a given item lands in a size-k weighted sample is genuinely useful but is not simply k · wi/Σw, and this page does not claim it is.