In reservoir sampling over a stream of unknown length, why keep item i with probability k/i?

## The problem the technique exists for You need k items drawn uniformly at random from a sequence whose length you will not know until it ends — or which never ends. A prize draw over a live clickstream is the shape: entries arrive one at a time, you cannot buffer them all, and at any moment someone may ask for the current winners. "Uniformly" here means that at the instant you are asked, after n items have gone past, every one of those n items is equally likely to be in your set of k, and every k-subset is equally likely. The obvious approaches both fail the constraints. Buffering the stream and choosing at the end costs memory proportional to the stream and cannot answer early. Counting the stream in a first pass and then picking k indices in a second pass needs a replayable, finite stream, which live traffic is not, and doubles the I/O when the data sits on remote storage. ## The algorithm Admit the first k items unconditionally. From then on, for the i-th item overall, keep it with probability `k/i`; if kept, choose one of the k residents uniformly and replace it. ``` for i in 1..k: reservoir[i] = next item of stream i = k while stream has more items: i = i + 1 x = next item of stream j = random_int(1, i) if j <= k: reservoir[j] = x ``` The single draw does double duty: `j <= k` happens with probability `k/i`, which is the keep decision, and the value of `j` names the victim uniformly among the k slots. ## Why k/i is the right number The invariant is: **after i items have been processed, each of those i items is in the reservoir with probability k/i.** It holds trivially at i = k, where all k admitted items are present with probability 1 = k/k. Assume it at i-1 and take the arrival of item i. The new item enters with probability `k/i` by construction, which is what the invariant demands of it. An existing resident survives in two disjoint ways: the arrival is rejected, probability `1 - k/i`; or the arrival is accepted, probability `k/i`, but the victim is one of the other k-1 slots, probability `(k-1)/k`. Adding them gives `1 - k/i + (k-1)/i = 1 - 1/i = (i-1)/i`. An item that was present with probability `k/(i-1)` is therefore present afterwards with probability `k/(i-1) x (i-1)/i = k/i`. The invariant is restored, and it holds after every single item — which is exactly why the length never has to be known. Stop the stream anywhere and the sample you are holding is uniform for the prefix you saw. The k = 1 case is worth tracing by hand: keep item i with probability `1/i`, replacing whatever you hold. After 3 items each has probability 1/3; the third by construction, the second as `(1/2)(2/3)`, the first as `(1)(1/2)(2/3)`. ## The boundaries that break it Three off-by-ones account for most broken implementations. Starting the probabilistic rule at item 1 instead of item k+1 is meaningless for i below k, where `k/i` exceeds one, and under-fills the reservoir. Counting i from zero rather than one shifts every probability by one item and biases the early arrivals. And evicting a fixed slot — the oldest, or slot 0 — rather than a uniformly chosen one destroys the survival term in the induction, producing a sample skewed toward recent items. A fourth is subtler: the reservoir must be reset per stream. Carrying one across two streams silently samples their concatenation. ## The cost lens One pass, O(k) memory regardless of stream length, O(1) work per item, and an answer available at any moment. The random draws dominate the per-item constant, and there is a refinement that removes most of them: rather than drawing once per item, draw how many items to *skip* before the next acceptance, since acceptances become rare as i grows. The expected number of replacements over n items is proportional to `k log(n/k)`, so the skip-based form does that many draws instead of n. ## Variants worth naming Weighted sampling drops out of a change of key: give each item the key `u^(1/w)` with u drawn uniformly from (0,1) and w the item's weight, keep the k largest keys in a size-k structure, and you have a one-pass weighted sample at O(log k) per item. Sharding works by bookkeeping: each shard runs its own reservoir and reports both its sample and how many items it saw. To merge, draw from the shard reservoirs in proportion to those counts. Without the counts the merge is wrong, because a shard that saw a thousand items and one that saw ten would contribute equally. Finally, the sample is random but should not be unrepeatable. Recording the seed alongside the result lets a disputed prize draw be replayed exactly, which is usually the difference between a technique and a technique you are allowed to ship.