UnipickerDraw Whitepaper
Algorithms · LESSON 5

Floyd sampling — preventing duplicate wins

Mass-entrant draw

When picking several people, the same person must not come up twice. Floyd is a clever way to remove duplicates cleanly, with no "redraw."

Key idea

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 does it work? The just-joined candidate is a number never drawn yet, so adding it never collides again. That is why no redraw is needed, and it is fast.
Compare

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.

5 of 6 people
Press the button several times. The number of tries jumps around each time, right? With bad luck it is far more. Floyd, in contrast, is always exactly 5 (0 wasted), so it is fast and predictable.
Concept

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.

So 5 − 3 + 1 = 3 — start from 3 candidates. Red = the candidate newly added that round.
Experiment

Follow One Round at a Time (3 of 5)

Press "Draw" to advance one round at a time. Each round adds one candidate.

Verify

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.

menu_bookReferences · Floyd sampling
  1. Bentley, J. L., & Floyd, B. (1987). Programming Pearls: A Sample of Brilliance. Communications of the ACM, 30(9), 754–757.
  2. Robert Floyd's Tiny and Beautiful Algorithm. nowherenearithaca.com
  3. A Sample of Brilliance. Fermat's Library. fermatslibrary.com/s/a-sample-of-brilliance