Pick Index - Reservoir Sampling

Reservoir sampling lets you pick one element uniformly from a stream without knowing the count beforehand.

Here's the algorithm: keep the first matching element. When you find the second match, replace your choice with probability $\frac{1}{2}$. For the third match, replace with probability $\frac{1}{3}$, and so on.

Why does this work? After seeing $k$ matches, your current choice has survived $k$ replacement tests, each with decreasing probability. The math shows each index has final probability $\frac{1}{k}$.