A stream begins.
You do not know whether it will contain one thousand events or one billion.
You are allowed to keep only one hundred examples.
Which hundred?
If you keep the first hundred, the beginning dominates.
If you keep the last hundred, the ending dominates.
Reservoir sampling gives every event a fair chance to survive.
Quick Read
Reservoir sampling is a family of one-pass algorithms for maintaining a fixed-size random sample from a stream whose total length may be unknown in advance. In classic Algorithm R, the first k items fill the reservoir. When the nth item arrives after that, it is admitted with probability k/n; if admitted, it replaces a uniformly chosen existing reservoir item.
The remarkable invariant is that after processing n items, every one of those n items has equal probability k/n of being in the reservoir.
One-sentence answer: reservoir sampling is lossy because almost every event is discarded, but the retained subset preserves an unbiased sampling relationship to the stream seen so far.
The Stream Length Is Unknown
If the full population size N were known and stored on disk, we could sample k indices uniformly and read those records.
Streaming changes the problem.
Items arrive once. Future length is unknown. Rewinding may be impossible or expensive.
The algorithm must decide online whether each new item deserves one of the scarce sample slots.
Algorithm R Begins by Filling the Reservoir
Let the reservoir hold k items.
The first k observations are inserted directly because there is still space.
At this moment every observed item is retained.
The lossy problem begins with item k+1.
The New Item Gets a Shrinking Chance
When the nth observation arrives, it enters the reservoir with probability k/n.
Early in the stream, that chance is relatively large.
Later, it becomes small because one fixed reservoir must represent an ever-growing history.
The probability shrinks exactly enough to keep every historical item equally represented in expectation.
Replacement Protects Fairness Across Time
If the new item is admitted, one existing reservoir slot is chosen uniformly for replacement.
That means old items gradually face removal as the stream grows.
No item receives permanent privilege merely because it arrived early.
History is continuously rebalanced.
Why Every Item Ends With the Same Inclusion Probability
The beautiful invariant can be seen inductively.
After n−1 observations, each earlier item is in the reservoir with probability k/(n−1).
At step n, an existing item survives unless the new item is admitted and happens to replace that particular slot.
The survival probability adjusts the old inclusion probability to k/n—the same inclusion probability as the newly arriving item.
The sample remains fair even though the algorithm never knew N.
Reservoir Sampling Is Not Downsampling
Downsampling usually reduces density along an ordered axis such as time, space or pixel position.
Reservoir sampling selects a random subset of records from a growing stream.
The first preserves coarse sequence or spatial structure. The second preserves sampling representativeness.
Different loss, different job.
Reservoir Sampling Is Also Not a Sketch
A Bloom filter keeps shared bit evidence.
HyperLogLog keeps register statistics.
A reservoir keeps actual source items.
That is an important distinction.
The representation is lossy because most items disappear, but the survivors remain inspectable examples rather than synthetic counters or centroids.
Why Keeping Real Examples Matters
Sometimes the receiver needs more than a statistic.
A debugging team wants representative traces.
A researcher wants records that can be inspected manually.
A teacher wants authentic student responses rather than only aggregate error counts.
A reservoir preserves raw examples inside a controlled memory budget.
The Sample Is Representative Only of What Entered the Stream
Reservoir sampling cannot repair upstream truncation.
If the stream itself excludes quiet users, failed sensors or absent students, an unbiased reservoir will faithfully sample that biased stream.
Random selection protects against temporal privilege inside the observed stream.
It does not make the observation pipeline representative of the world automatically.
Rare Events Can Still Be Missed
A uniform reservoir of 100 from one billion events is tiny.
If a critical event occurs once in a million, the reservoir may contain none.
This is not algorithmic bias. It is sampling variance.
If rare events matter disproportionately, stratified, weighted or targeted sampling may be needed alongside a uniform reservoir.
Weighted Reservoir Sampling Changes the Definition of Fair
Not every item must deserve equal inclusion probability.
A weighted reservoir can give more important or more informative items greater chance of survival.
That can be exactly right when importance is known and justified.
It also creates a new responsibility: the weights now define whose reality is more likely to survive.
Distributed Reservoirs Need Careful Merging
Suppose several machines each maintain a reservoir.
Simply taking equal numbers from each local reservoir can bias the global sample if the machines processed different stream volumes.
Correct merging must account for the population each local reservoir represents.
Mergeability is not automatic merely because every local sample was fair.
Logging Systems Use Sampling Because Full Retention Can Be Impossible
A high-traffic service can generate enormous volumes of traces.
Retaining everything may be economically or technically impossible.
A reservoir can preserve a representative set of real traces for inspection.
But if operational incidents live in rare tails, uniform sampling alone may be insufficient. Systems often preserve errors, slow requests or anomalous traces through separate rules.
Education: A Portfolio Is a Reservoir Only if Selection Is Honest
A student produces hundreds of pieces of work.
A portfolio contains ten.
If the ten are only the best pieces, the portfolio is not a representative sample of learning.
If pieces are selected to cover time, topics, errors and improvement, the portfolio becomes a more deliberate representation.
Reservoir sampling teaches the mathematical extreme: fairness can be designed into which examples survive.
When Reservoir Sampling Is Exactly the Right Loss
Use it when the stream length is unknown, only a fixed number of real examples can be retained, uniform inclusion is appropriate, and later human inspection of actual source records matters.
It is particularly strong when the receiver needs examples rather than only statistics.
When Reservoir Sampling Becomes Dangerous
- Rare but critical events require guaranteed capture.
- The incoming stream is already biased or truncated.
- Weighted sampling is used but the weights are poorly justified.
- Distributed reservoirs are merged without population-size correction.
- The sample size is too small for the downstream inference.
- The reservoir replaces records that law, science or safety requires to be retained exactly.
A Practical Reservoir-Sampling Audit
- Population: what stream is actually being sampled?
- Reservoir size: how many examples survive?
- Inclusion: should all observed items have equal probability?
- Rare events: do critical minorities need separate capture rules?
- Merge: how are distributed samples combined?
- Inspection: are retained items preserved with provenance?
- Retention: which records must never be discarded?
Sources and Further Reading
- Jeffrey S. Vitter’s classic reservoir-sampling work, including Algorithm R and later efficient variants.
- Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))).
Continue Through eduKateSG
Continue with How Lossy Works | Sampling, How Lossy Works | Truncation, and How Lossy Works | Probabilistic Sketches.
Final Thought: Fair Forgetting Is Still Forgetting
Reservoir sampling does not preserve the stream.
Its achievement is subtler.
It gives every observed event a principled chance to remain after memory runs out.