How to Learn Reservoir Sampling: One-Pass Random Selection, Unknown Stream Length and Uniform Guarantees

Wait, What?

You can choose a uniform random sample from a stream even when you do not know how long the stream will be.

Reservoir sampling solves a deceptively difficult problem: maintain a random sample while records arrive one by one, without storing the entire history and without knowing the final number of records in advance. The core method is small enough to trace by hand, yet rich enough to teach probability invariants, streaming constraints and proof by induction.

Quick Answer

For a reservoir of size k, keep the first k items. When the i-th later item arrives, give it probability k/i of entering the reservoir; if it enters, replace one of the current k items uniformly. After processing i items, every item seen so far has probability k/i of being in the reservoir.

1. Start With k = 1

The cleanest beginner case keeps one sample. Accept the first item. For item i, replace the current sample with probability 1/i. Trace the first four arrivals using fixed random numbers. Then ask the learner: after four items, what is the probability that the first item remains? The answer should be 1/4, not because we stored all four but because each later survival probability multiplies correctly.

2. Generalise to a Reservoir of Size k

Store the first k items. For each subsequent position i, decide whether the new item enters with probability k/i. If chosen, replace one uniformly selected reservoir position. This separates two random decisions: whether the incoming item joins and, if so, which existing item leaves.

3. Learn the Invariant, Not the Recipe

The key invariant is: after processing i items, every one of those items has equal inclusion probability k/i. For the new item, this is true by direct construction. For an old item, combine its previous inclusion probability with the probability that it is not the one replaced. This gives a compact induction proof that the sample remains uniform.

4. Why Streaming Changes the Problem

If the entire dataset fits in memory and its size is known, many other sampling methods are available. Reservoir sampling matters because it works under a different contract: one pass, bounded retained state and possibly unknown final stream length. Learners should always state that contract before claiming the algorithm is needed.

5. Test Uniformity Empirically

Run the algorithm many times on a tiny stream with different seeds and count how often each item appears. The frequencies should approach the theoretical inclusion probability. This is not a proof, but it is a useful calibration exercise: proof establishes the guarantee; simulation checks the implementation.

6. Learn Faster Variants Only After Algorithm R

The classic simple method is often called Algorithm R. Jeffrey Vitter later developed methods that skip over runs of items rather than generating a replacement decision for every record, improving efficiency for large streams. Advanced learners should first master the probability invariant of the simple method, then study why skip-based methods can preserve the same sampling contract with less random-number and per-item work.

7. Weighted and Distributed Variants Are Different Jobs

Uniform reservoir sampling gives each item equal probability. Weighted sampling changes the target distribution. Distributed sampling adds mergeability and partition concerns. Do not casually reuse the uniform proof when the sampling contract changes.

Common Failure States

• Choosing every later item with fixed probability instead of k/i.
• Replacing an existing reservoir item non-uniformly.
• Assuming empirical frequencies prove correctness.
• Forgetting that the guarantee depends on suitable randomness.
• Using the uniform algorithm for a weighted-sampling requirement.
• Claiming constant memory without stating that the reservoir itself uses O(k) storage.

Practice Ladder

• Trace k = 1 on four items.
• Prove the inclusion probability of the first item after each arrival.
• Generalise to k > 1.
• Implement and simulate frequencies across many seeds.
• Compare with sampling after storing the full dataset.
• Explain when skip-based reservoir methods become useful.
• Identify when weighted or distributed sampling requires a different method.

Learning Hall Boundary

This article owns uniform reservoir sampling and its streaming probability invariant. It connects to the existing streaming-algorithms and sketching articles without taking over their broader jobs. Sampling selects representative records; sketches usually estimate aggregate properties using compressed summaries.

Evidence Boundary

The mathematical uniformity guarantee assumes the random choices are generated according to the stated probabilities. Real systems should also consider pseudorandom-number quality, reproducibility, parallel ingestion, adversarial ordering and whether uniform sampling is actually the desired statistical objective.

Professional rule: understand reservoir sampling when you can derive the k/i replacement logic, prove equal inclusion probability after every prefix of the stream, and state exactly which streaming constraint makes the method useful.