Why architecture matters here
The architecture matters because the constraints it satisfies — one pass, bounded memory, unknown length — are precisely the constraints of real streaming systems, and no simpler method meets all three. Buffering the whole stream and sampling at the end needs O(n) memory and a known end; sampling each item independently with a fixed probability p gives a sample whose size varies randomly and which you cannot cap; two passes are impossible over a stream you can read only once. Reservoir sampling is the answer that fits the shape of the problem: fixed memory, fixed output size, single pass, no advance knowledge of n.
It works because it continuously rebalances the sample's fairness as the stream grows. Early items are easy to keep — when only ten items have arrived and k is five, each has a high chance of being in the reservoir. But as more items arrive, each early item's right to remain must shrink so that late arrivals get their fair share. The retention probability k/i encodes exactly this: it makes each new item's admission chance decline as 1/i while simultaneously diluting the incumbents at just the rate that keeps every item at the same final probability k/n. The elegance is that this fairness is maintained incrementally, with a single random draw per item and no bookkeeping about what came before.
The reason it needs to be understood rather than copied is that small deviations silently break uniformity. Use the wrong probability, reuse a weak random source, or mishandle the fill phase, and the sample becomes biased in ways that no assertion will catch — the code runs, produces k items, and quietly over-represents early or late arrivals. Because the guarantee is probabilistic and the bias is subtle, the correctness lives in the math, and knowing why k/i is the right value is what lets you adapt the algorithm (to weights, to shards, to skips) without destroying the property that makes it worth using.
A concrete use makes the constraints vivid. A service handling a hundred thousand requests a second wants to keep a live sample of a thousand recent request traces for debugging — but it cannot store every trace, and it cannot know in advance how many requests a given window will contain. A thousand-slot reservoir solves it exactly: each incoming trace is considered once, the reservoir always holds a uniform sample of everything seen so far, and memory is fixed at a thousand traces no matter whether the window saw a million requests or a billion. An engineer investigating an incident reads the reservoir at any instant and gets a representative, unbiased snapshot — not the most recent thousand, not the first thousand, but a fair draw across the whole stream. That 'fair draw at fixed cost, readable at any time' is a capability no buffer-and-sample or fixed-probability scheme can offer over an unbounded flow.
There is also a scaling story that makes the algorithm more than a textbook curiosity. Because the reservoir summarizes an unbounded stream in fixed space, it composes: independent reservoirs over shards of a stream can be merged into a single uniform reservoir over the whole, so the sampling parallelizes across machines. And because the per-item work is a single comparison in the common case, the algorithm keeps up with high-throughput streams where anything heavier would fall behind. Those two properties — mergeability and constant per-item cost — are what let reservoir sampling sit in the hot path of a real telemetry or analytics pipeline rather than only in an interview question.
The architecture: every piece explained
The reservoir is a fixed array of k slots holding the current sample. Its size never changes; the entire algorithm is about which items occupy those k slots at any moment. Memory is O(k) regardless of how long the stream runs, which is the whole point — you can sample a billion-item stream into a thousand-slot reservoir on a laptop.
The fill phase handles the first k items trivially: they go straight into the reservoir, one per slot, with no randomness. Until you have seen k items there is nothing to choose — every item so far must be in a sample of size k. This phase establishes the base case for the uniformity invariant: after exactly k items, all k are in the reservoir with probability 1, which is k/k, consistent with the k/i rule.
The replace phase begins with item k+1 and runs to the end. For the i-th item, the algorithm draws a random integer j uniformly in the range 1..i. If j is at most k, item i enters the reservoir and overwrites slot j — evicting whatever was there; if j exceeds k, item i is discarded. The probability that j ≤ k is exactly k/i, which is therefore the chance the new item is admitted, and because the evicted slot is chosen uniformly, every current occupant is equally likely to be the one replaced. That symmetry is what keeps the incumbents fair as they are diluted.
The retention probability k/i is the load-bearing quantity, and it is worth stating precisely what it governs. It is the probability that item i, at the moment it arrives, is admitted to the reservoir — declining as the stream grows so late items do not crowd out early ones, yet high enough that late items are represented at all. Its counterpart is the survival of incumbents: an item already in the reservoir survives item i with probability 1 − (k/i)(1/k) = 1 − 1/i, and the product of these survival terms across the rest of the stream is exactly what dilutes an early item down to the same final k/n as everyone else. The invariant that ties it together — every item present with probability k/n after n items — is not an assumption but a theorem, and the next section proves it by induction. Understanding that k/i is the unique value making the induction close is what separates using the algorithm from merely memorizing it, because every variant (weighted, distributed, skip-based) is derived by preserving that same closure under a changed rule.
End-to-end flow
Follow the invariant through a step to see why it holds. Claim: after processing i items, each of them is in the reservoir with probability k/i. Base case: after i = k items, the fill phase put all k in, each with probability 1 = k/k. Inductive step: assume the claim holds after i−1 items, and process item i. The new item i is admitted with probability k/i by construction — so it satisfies the claim immediately. Now consider an older item that was in the reservoir after i−1 steps, where by hypothesis it was present with probability k/(i−1).
That older item stays in the reservoir after step i unless item i both is admitted and happens to evict it. Item i is admitted with probability k/i, and if admitted it evicts a uniformly chosen one of the k slots, so it evicts our specific item with probability 1/k. The chance our older item is evicted is therefore (k/i)(1/k) = 1/i, and the chance it survives is 1 − 1/i = (i−1)/i. Its probability of being in the reservoir after step i is thus its prior presence times its survival: k/(i−1) × (i−1)/i = k/i. Every item — the new one and every old one — is now present with probability k/i, so the invariant holds after step i, and by induction it holds for all n.
Trace the mechanics on a concrete stream with k = 2. Items 1 and 2 fill the reservoir. Item 3 draws j in 1..3; with probability 2/3 (j is 1 or 2) it replaces that slot, else it is dropped — every one of items 1, 2, 3 now sits at probability 2/3. Item 4 draws j in 1..4; admitted with probability 2/4 = 1/2, evicting a random incumbent. After item 4, checking any item gives probability 2/4 = 1/2, exactly k/n. No matter where the stream stops, the two slots hold a uniform pair.
Watch how the design meets its constraints along the way. Each item is touched once, in arrival order, so the pass is single and forward-only — perfect for a cursor or a socket. The only state is the k-slot array and a running count i, so memory is bounded no matter how long the stream runs. And n never appears in the logic — the algorithm can be stopped at any moment and the reservoir is a valid uniform sample of everything seen so far, which is precisely what you want for a monitor that must always have a representative snapshot on hand. The end-to-end flow is thus a running, always-valid, fixed-cost sample of an unbounded flow — and the proof is what guarantees that 'always valid' is literally true at every step, not just at the end.