Reservoir Sampling

Uniform Sample From a Stream

1:00

How to draw a perfectly uniform random sample of k items from a stream of unknown length using only O(k) memory and a single pass.

By the end, you can

Explain why knowing n in advance is not required for uniform reservoir sampling.
Trace Algorithm R step-by-step for a small stream and state the selection probability at each step.
Verify the fairness invariant algebraically: show that k/(i-1) × (1 − 1/i) simplifies to k/i.
State the time and space complexity of Algorithm R and explain why they are O(n) and O(k) respectively.
Describe how Algorithm L cuts the number of random draws from O(n) to O(k log(n/k)).
Explain the A-Res key formula u^(1/w) and why a larger weight produces a larger expected key.

Up next in String Algorithms, Advanced DP & Competitive Techniques