A stream can be too long to store, and its final length may be unknown when the first item arrives. Reservoir sampling maintains a small, exact uniform sample of the items seen so far. We then use that sample to estimate a property of a fixed stream, making the randomness and its limits explicit.
Keeping a sample while the stream grows
Fix an integer capacity . Number stream occurrences ; equal values at different positions remain distinct occurrences. Store the first items in slots. On item , independently of previous draws, choose uniformly from . If , replace slot by item ; otherwise leave the reservoir unchanged. When fewer than items have arrived, keep all of them. The final length need not be known in advance.
Theorem 9.1.1
(Reservoir uniformity)
Run the reservoir algorithm with capacity on a fixed stream. For every , after items the set of occurrence indices in the reservoir is uniformly distributed over the subsets of of size .
Proof
(Induction on the stream length)
For a fixed stream and every , the reservoir's set of occurrence indices is uniform among the subsets of size . At there is only one such subset. Suppose the claim holds at and fix a target set of size .
If , the previous reservoir must be and no replacement may occur. The first event has probability by the induction hypothesis, and no replacement has probability , independently. The product is
Since , this is exactly .
If , the previous reservoir must contain and one of the earlier indices outside . For each such previous set, which has probability , the probability that the one extra item occupies the slot selected for replacement is , regardless of its slot position. Thus the total is again . This covers both cases and completes the induction.
Proof X-ray
Why the two cases give the same number
The proof has one move: split the target set by whether it contains the newest index , so that the induction hypothesis can be applied to the previous reservoir in each case. The hypothesis is used twice, each time only through the fact that every size- subset of has the same probability .
The two cases are different events and the same arithmetic closes them. If , one previous set works and survives with probability . If , there are previous sets, each reaching with probability because the new item must land in one specific slot out of equally likely values of . Both products equal , which is . The count is exactly the number of earlier indices outside , and this is why the counts of the two cases match.
The replacement probability is essential. If a new item replaced a slot with some other fixed probability , the case would give , equal to only for . Freshness of is also used: it is independent of the past, so the transition probabilities multiply. Treating equal values as the same item is not allowed, since the statement is about occurrence indices.
Estimating a fraction
Fix a stream of length independently of the sampling randomness. Attach a fixed indicator to each occurrence, and write . Let be the mean of the stored indicators. Uniform sampling without replacement gives . When ,
To derive this, let be the indicator at the th position of a uniformly random ordering of the population. Each has variance . For distinct positions, , where is the number of ones, so their covariance is . The average of the first positions has the stated variance. If , the reservoir contains the only item, so its variance is zero; the displayed formula has a zero denominator and is not used.
Chebyshev's inequality gives, for and ,
The upper bound may exceed one and then carries no information. At the sample is the whole stream and the estimate is exact. The fixed-stream assumption matters: a later item or stopping rule chosen in response to revealed reservoir contents is a different adaptive model and is not covered by this proof.
Four occurrences
Worked example 9.1.2
(Four occurrences, two slots)
Take , and indicators . The six two-index subsets are equally likely. One gives , four give , and one gives . The population fraction is , while . For , the probability of an error at least is , equal to the exact variance-based bound in this case.
Counterexample mode
Uniform individual inclusion is not independence
A natural but false claim: if every occurrence is stored with probability , the inclusion indicators behave like independent coins of that bias. Test it with , . Each of the six two-index subsets has probability , so each occurrence is included with probability . Independence would give , but the true value is , the single subset . The covariance of those two indicators is . The sum of the four indicators is always , so its variance is , whereas four independent indicators of bias would give variance . For the stream , treating the draws as independent gives , while the true value is . The repair is to use the exact without-replacement variance with the finite-population factor .
The algorithm stores at most items and a counter for the stream position. Under an ideal uniform-integer draw model, it uses one draw per item after the first ; the bit cost and storage for item values depend on their representation and on the implementation of that draw. It estimates a fixed finite-stream fraction; it does not automatically estimate a future data distribution or handle adversarial adaptation.
Common mistake
(Entering with probability for every capacity)
For the new item enters with probability , and it is tempting to keep that rule for larger , choosing the slot to overwrite uniformly. Take and : item then enters with probability , while items and each survive with probability . A uniform size- subset of contains each index with probability , so this rule is biased toward early items. The algorithm above draws uniformly from and replaces only when , so item enters with probability and lands in each slot with probability .
Exercises
Quick check
(If , what is ?)
Solution · Answer
Exactly : the reservoir holds every occurrence, so the sample mean is the stream mean.
Quick check
(In the four-occurrence example, what is the probability that a particular occurrence is stored?)
Solution · Answer
: three of the six equally likely two-index subsets contain that occurrence.
Quick check
(At , , what is the variance of ?)
Solution · Answer
Zero, since the reservoir always holds the only item; do not substitute into the formula with denominator .
Quick check
(Does a uniform size- sample require independent inclusion indicators?)
Solution · Answer
No; a fixed sample size generally makes them dependent. In the four-occurrence example two given occurrences are both stored with probability , not .