Suppose I have a sequence of $n$ values. I would like to take sample of $k$ of these, uniformly at random (without replacement preferably, but with replacement if that's easier).
The obvious solution would be to generate $k$ random integers in $[0..n]$, then to take the value at each of those indices. But there's an additional trick: I can't take arbitrary elements from the sequence. I have to run through the sequence in order, choosing whether to take each one as I come to it, then moving on (like in the secretary problem).
After I go through all $n$ samples, I can go back to the beginning and try again. But doing so is expensive, so I'd prefer to do this as few times as necessary.
One straightforward solution with this constraint is to take each element with probability $\frac{k}{n}$ and repeat until I have $k$ accumulated. But this doesn't give a uniform distribution: elements at the beginning are more likely to be picked than elements at the end.
What's the optimal strategy here, i.e. the strategy that runs through the list as few times as possible?
There's no reason we can't keep track of more along the way - so keep track of how many more samples we need and how many possibilities are left. We take the first with probability $\frac{k}{n}$, the second with probability either $\frac{k}{n-1}$ or $\frac{k-1}{n-1}$ depending on whether we took the first, and so on.
Or, for a physical representation - take a deck of $n$ cards, and pick $k$ of them to be the ones we choose. Shuffle the deck, then take one card for each secretary as we go through the list. Choose them if we've got one of the good cards, skip over them otherwise.
If $k$ is relatively small and random numbers are expensive, we can generate our $k$ random numbers in advance, then sort them.
Any of those ideas are one pass through the list.