How reservoir sampling picks a fair sample from an endless stream
How an algorithm can keep a truly random sample of k items from a stream whose length it never knows, using one pass and a fixed amount of memory.
Written by Amili, an AI writer, from the sources listed below · 24 October 2026 · 5 min read
Reservoir sampling is a family of randomized algorithms that maintain a simple random sample of k items from a stream of unknown length, in a single pass. At every moment the kept items are a fair sample of everything seen so far, without storing the whole stream.
In short
- The algorithm sees each item once, cannot look back, and never knows the total length in advance.
- A fixed-size reservoir holds the sample; each new item replaces an old one with a carefully chosen probability.
- At every step, every item seen so far has the same chance of being in the sample.
- Faster variants skip ahead in the stream instead of rolling a random number for every item.
- Weighted versions let some items be more likely to be chosen than others.
What problem does reservoir sampling solve?
A simple random sample is a subset chosen so that every possible group of k items is equally likely. With a list in hand, that is easy: number the items and draw k at random. The difficulty comes when the items arrive one by one, the total is unknown, and there is far too much data to keep in memory.
Reservoir sampling handles exactly this situation. The population is revealed over time, the algorithm cannot go back to earlier items, and yet whenever it is stopped, the items it holds must form a fair sample, without replacement, of everything seen up to that point. A sampling method that did not need the population size in advance was described as early as 1962.
How does Algorithm R work, step by step?
The best-known version, Algorithm R, is short. First, put the first k items of the stream into an array; this is the reservoir. Then, for each later item, pick a random whole number between 1 and the item's position in the stream. If that number is k or smaller, the new item overwrites the reservoir slot with that number. Otherwise the new item is thrown away. When the stream ends, the reservoir is the sample.
The effect is that the item at position i gets into the reservoir with probability k divided by i. Early items are almost certain to enter but face many later chances of being pushed out; late items rarely enter but face few threats afterwards. These forces balance exactly, so every item ends with the same chance of surviving. Algorithm R can also be seen as a variation on the Fisher-Yates shuffle.
What does a small worked example look like?
Take the simplest case, a reservoir of one item. Keep the first item. When the second arrives, swap it in with probability one half. When the third arrives, swap it in with probability one third, and so on, so the item at position i replaces the current choice with probability 1 divided by i.
Check it after three items. The third item is held with probability one third. The second item had to win its coin flip (one half) and then survive the third round (two thirds), which multiplies to one third. The first item had to survive both rounds: one half times two thirds, again one third. All three are equally likely, and the same reasoning, applied by induction, works for any number of items and any reservoir size.
How can it be made faster, and where is it used?
Algorithm R draws a random number for every single item, so its running time grows in step with the stream. Jeffrey Vitter observed that an algorithm allowed to jump over stretches of the stream without inspecting them can do better, and he showed an approach with optimal running time. Kim-Hung Li later gave a simpler method, Algorithm L, with the same performance. The trick is that the number of items skipped before the next replacement follows a geometric distribution, so the algorithm can draw that gap directly and leap ahead, spending effort only on items that actually enter the reservoir.
Some applications want items chosen according to weights. A search engine might sample its queries in proportion to how often each was run, to study overall impact on users. Algorithms such as A-Res and A-ExpJ, from Efraimidis and Spirakis, give each item a random key shaped by its weight and keep the k items with the best keys. In machine learning, a variant called KLRS adjusts a stream buffer toward a target mix of classes, to help with imbalanced data during continual learning.
Where does it fail or get misused?
Reservoir sampling assumes the sample itself fits in memory, which usually means k is a fixed number regardless of how long the stream runs. If the goal is to keep a large fraction of the input, such as a third of it, other methods are needed, including distributed approaches.
A fair sample also does not guarantee a representative one. Simple random sampling is unbiased on average across many draws, but any single sample can still miss parts of the population by chance. Weighted variants must be chosen carefully as well: different algorithms interpret weights differently, and a common description of one weighted method has been flagged as wrong when checked against the original paper.
What does reservoir sampling teach about thinking?
Reservoir sampling shows that fairness can be maintained continuously rather than calculated at the end. It does not need to know the future to treat the past evenly; it only needs to give each newcomer the right odds. That is a useful antidote to judging by whatever arrived most recently or whatever happened to come first. It also illustrates a broader habit: when the whole picture is too big to hold, a carefully drawn small sample can stand in for it, as long as the drawing is genuinely random.
Questions people ask
Why is reservoir sampling called reservoir sampling?
The name refers to the fixed-size array that holds the current sample, called the reservoir. Items flow past in the stream, and some of them are drawn into the reservoir, displacing items already there. The reservoir never grows beyond k slots, which is why the method can process streams far larger than the available memory while always holding a usable sample.
Does every item really have an equal chance of being chosen?
Yes, in the standard unweighted versions. After i items have arrived, each of them is in a k-slot reservoir with probability k divided by i. The proof works by induction: assume it holds after one item, then show the replacement rule keeps all probabilities equal when the next item arrives. Weighted versions deliberately change this so heavier items are favoured.
What is the difference between sampling with and without replacement here?
Without replacement, each input item can appear in the final sample at most once, which is the usual goal. With replacement, the same item may appear more than once. For a sample of size one the two give the same distribution, and skip-based algorithms exist for the with-replacement case, including a very simple one for a single-item reservoir.
The thinking behind it
Sources
- Reservoir sampling — Wikipedia
- Simple random sample — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.