Floyd sampling — preventing duplicate wins
Mass-entrant drawWhen picking several people, the same person must not come up twice. Floyd is a clever way to remove duplicates cleanly, with no "redraw."
Floyd's one-line secret
Grow the candidate pool by one and draw. But if the number drawn is already a winner? Do not redraw — give that spot to the "candidate that just joined."
Why is plain "redraw" hard?
The easiest way is "if a draw is already a winner, drop it and draw again." But because it is random, bad luck can make the same person come up over and over. Then nobody knows how many redraws it will take (unpredictable).
Especially when almost everyone is picked and few seats remain, only already-won people keep coming up, so you can repeat wasted redraws a huge number of times.
Why start from "3" when there are 5?
We are picking 3 people, so we only draw 3 times. And in the last round all 5 must be candidates to be fair. In the last (3rd) round there are 5 candidates, and each earlier round has one fewer: 5 → 4 → 3. So the first round starts with 3 candidates.
Follow One Round at a Time (3 of 5)
Press "Draw" to advance one round at a time. Each round adds one candidate.
Why is it fair? — check for yourself
An earlier number has more chances to be drawn; a later number gets drawn instead when a duplicate occurs. The two cancel out exactly, so everyone has the same probability (picks ÷ people).
Draw 3 of 8 five thousand times and compare each entrant's win count.
- Bentley, J. L., & Floyd, B. (1987). Programming Pearls: A Sample of Brilliance. Communications of the ACM, 30(9), 754–757.
- Robert Floyd's Tiny and Beautiful Algorithm. nowherenearithaca.com
- A Sample of Brilliance. Fermat's Library. fermatslibrary.com/s/a-sample-of-brilliance
