What you're seeing
We run the sampler over and over on the same n-item stream and tally how often each item survives into the final sample of size k. Each bar is one item's empirical probability of being chosen. The claim is that every item — first or last, it doesn't matter — ends up with the same chance, k/n. Watch the bars, jittery at first, settle onto the dashed line and turn green: that flatness is the uniformity guarantee, measured.
The rule
reservoir(stream, k):
res = first k items
for i = k, k+1, …: # i is 0-based index of the next item
j = random integer in [0, i]
if j < k:
res[j] = stream[i] # evict slot j, keep the new item
return res
The magic number is k/(i+1) — the probability the i-th item is kept. It needs no knowledge of the stream's length and never looks back.
The invariant
The guarantee holds at every prefix, not just the end: after processing i items, each of them is in the reservoir with probability exactly k/i. Induction makes it precise. It is clearly true after the first k items (all are in, probability k/k = 1). Assume it holds after i items; the (i+1)-th item is kept with probability k/(i+1) ✓. An old item, previously in with probability k/i, stays unless it is the evicted slot: it survives with probability k/i · (1 − (k/(i+1))·(1/k)) = k/i · (i/(i+1)) = k/(i+1) ✓. So after all n items, every item's probability is k/n — uniform, and the early items are not favored despite having been in the reservoir longer. That cancellation is the whole trick.
The cost
The point is the O(k) space and the single pass: you can sample from a stream far larger than memory, or one whose length you never learn, holding only the k chosen items and a counter. (Vitter's Algorithm L improves the time to O(k·(1+log(n/k))) by skipping ahead to the next item that will be kept, but Algorithm R, shown here, is the clearest statement of the idea.)
In the wild
Reservoir sampling is the standard way to take a fair sample from a firehose: k random rows from a huge log or database scan, a uniform sample of tweets or click events for analytics, random minibatches from a dataset streamed once, and "sample N lines" tools. It shines exactly when you can't store everything or don't know n in advance — a single pass, constant memory, provably unbiased. Weighted variants (the A-Res / exponential-jump algorithms of Efraimidis–Spirakis) extend it to non-uniform sampling for things like importance-weighted streams.
Try this
Set Simulated runs low and watch the bars jump around — a few hundred runs isn't enough to see uniformity. Crank it up and they flatten onto the k/n line. Then change k: the whole line jumps to the new k/n, and every item still lands on it. The first item is no more likely than the last — that's the fairness the invariant guarantees.
References
- Vitter, J. S. "Random sampling with a reservoir." ACM Transactions on Mathematical Software 11(1):37–57, 1985. Algorithms R and L.
- Knuth. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §3.4.2 (Algorithm R). Addison-Wesley.
- Efraimidis, P. & Spirakis, P. "Weighted random sampling with a reservoir." Information Processing Letters 97(5):181–185, 2006 — the weighted variant.