Randomized Algorithms

Perfect Shuffle & Reservoir Sampling

Two classic problems share the same core goal: distribute probability mass perfectly evenly across all possible final outcomes.

1 · Random permutation

Fisher–Yates Shuffle

At index i, choose j ∈ [0, i] uniformly and swap.
O(n) time · O(1) space
Current array i = 5
There are 6 equally likely choices for j.
Why is it uniform?

For one particular final permutation, the algorithm must make exactly one correct choice at each stage:

P(one permutation)
= 1/n × 1/(n−1) × ··· × 1/2
= 1/n!

Because every permutation corresponds to one unique sequence of these choices, every one of the n! permutations has the same probability.

2 · Unknown-length stream

Reservoir Sampling (k = 1)

When item i arrives, keep it with probability 1/i.
O(n) time · O(1) space
Reservoir
—
Items seen
0
Incoming stream replacement probability = —
Press “Next item” to start the stream.
Why does every item finish with probability 1/n?

Suppose item k enters the reservoir when it arrives. It must then survive every later replacement opportunity:

P(finally keep item k)
= 1/k × k/(k+1) × (k+1)/(k+2) × ··· × (n−1)/n
= 1/n

The middle factors cancel. So every stream item has the same final probability.

The shared idea

Uniformity by carefully balancing probability

Fisher–Yates

Fix one position at a time while choosing uniformly from the remaining items.

↔
Reservoir Sampling

Rebalance selection probability every time a new stream item appears.

Problem Solution Uniform? Time Space
Random permutation of n items Fisher–Yates Shuffle Yes O(n) O(1)
Sample one item from a stream Reservoir Sampling (k = 1) Yes O(n) O(1)