reservoir sampling

Imagine items flowing past you one at a time on a conveyor belt, and you must keep exactly one of them chosen uniformly at random — but you do not know in advance how many items there are, and you can only hold one at a time. You cannot count them first and then pick. Reservoir sampling is the elegant rule that solves this: keep a current pick, and as each new item arrives, replace your pick with it with just the right probability so that, at any moment, your held item is a uniformly random choice from all items seen so far.

Precisely, for choosing one item: keep the first item as your sample; when the t-th item arrives (for t = 2, 3, ...), replace your stored sample with the new item with probability 1/t, otherwise keep what you have. After processing n items, every one of them is your final sample with probability exactly 1/n. The proof is a clean induction: item t becomes the sample with probability 1/t at its arrival, and survives each later step j with probability (1 - 1/j) = (j-1)/j; multiplying its acceptance by its survival through steps t+1,...,n telescopes, (1/t) times (t/(t+1)) times ((t+1)/(t+2)) times ... times ((n-1)/n) = 1/n. So all n items are equally likely. To keep a sample of size k instead of 1, keep the first k items, then for the t-th item (t > k) keep it with probability k/t and, if kept, have it evict a uniformly random one of the current k.

Reservoir sampling matters because it draws a uniform sample in a single pass using O(k) memory, with no need to know or store the stream length — perfect for huge logs, network packets, or data too big to hold. It is the canonical 'online' sampling method. The honest caveat: it gives a uniform sample without replacement and assumes you can generate fair random numbers; weighted versions and sampling with replacement need different rules. And while the expected behavior is exact, any single run is one random draw, so to estimate quantities you still combine many samples or use concentration bounds.