Randomized Algorithms

Reservoir sampling, rejection sampling, and Fisher–Yates shuffling use randomness to solve sampling problems correctly and efficiently.

1. The idea

Reservoir sampling selects a uniform random sample of size $k$ from a stream of unknown or unbounded length using $O (k)$ memory: keep the first $k$ items, then for the $i$ -th item ( $i > k$ ), replace a random existing item with probability $k / i$ . This guarantees every item ends up with equal probability $k / n$ of being in the final sample.

Rejection sampling generates samples from a target distribution by sampling from an easier proposal distribution and accepting/rejecting based on a ratio, useful when direct sampling from the target is hard but you can bound it by a scaled proposal density.

The Fisher–Yates shuffle produces a uniformly random permutation of an array in $O (n)$ time by iterating from the last element to the first, swapping each with a uniformly random earlier-or-equal-index element — a naive 'swap with any random index' approach does not give a uniform distribution over permutations.

2. Why it matters

These algorithms show up in quant-dev interviews testing whether you understand correctness of randomization, not just implementation — a subtly biased shuffle or sampler is a classic interview trap.

3. Core mathematics

Reservoir sampling acceptance probability (item i, i>k)

P (item i replaces a slot) = \frac{k}{i}

Each item ends with probability k/n of being retained

Rejection sampling acceptance probability

P (accept) = \frac{f ( x )}{M g ( x )}

$f$ target density, $g$ proposal density, $M$ = bound s.t. $f (x) \leq M g (x)$

Fisher–Yates shuffle (0-indexed)

for i = n - 1 down to 1 : j \sim Uniform {0, \dots, i}, swap a [i], a [j]

4. How to recognize it

Think of this when…

Stream of unknown length and need a uniform random sample without storing everything
Need to sample from a distribution you can't invert directly but can bound
Asks to shuffle an array 'fairly' or prove a shuffle is uniform

5. Worked example

Worked example

Using reservoir sampling with k=1, verify that after processing a stream of n=4 items, each item has probability 1/4 of being the final sample.

1
Item 1 starts as the reservoir (prob 1 of being current holder).
$P_{1} (held after item 1) = 1$
2
Item 2 replaces with probability 1/2; item 1 survives with probability 1/2.
$P (item 1 survives step 2) = 1/2$
3
Item 1 survives step 3 (replaced w.p. 1/3, survives w.p. 2/3) and step 4 (survives w.p. 3/4).
$P (item 1 final) = 1 \times \frac{1}{2} \times \frac{2}{3} \times \frac{3}{4} = \frac{1}{4}$
4
By symmetry of the algorithm's construction, every item ends with the same 1/4 probability.
$P_{i} (final) = \frac{1}{n} = \frac{1}{4} \forall i$
Answer: Each of the 4 items has exactly probability 1/4 of being the final sample, confirming uniformity.

6. Common mistakes

Implementing a shuffle by swapping each element with a uniformly random index from the *entire* array (not just i..n-1), which is biased, not uniform
Using reservoir sampling with the wrong replacement probability (e.g. always 1/n instead of k/i at step i)
In rejection sampling, choosing too loose a bound M, making the algorithm correct but extremely inefficient (low acceptance rate)

7. Quick check

Reservoir sampling with k=1 replaces the current sample with the i-th item (i>1) with probability:

A 'shuffle' that swaps each index i with a uniformly random index from the whole array (0 to n-1, not i to n-1) produces:

8. Practice

5 QuantSolve questions use this concept.

Practice this concept

9. Related methods

This lesson is conceptual; see the topic hub for methods.

Create a free account to save lesson progress.