If you break early, then you haven't given items later in the list the chance to be selected. You need to go through the entire list in order for every item to

If you break early, then you haven't given items later in the list the chance to be selected. You need to go through the entire list in order for every item to have an equal probability of selection. I didn't get it at first, either, and the Wikipedia article didn't do it for me. This explanation finally got me there: https://florian.github.io/reservoir-sampling/ https://florian.github.io/reservoir-sampling/