Algorithms · LESSON 4
Reject unfair numbers
Weighted interval drawMass-entrant drawHow do you fairly pick from 5 friends with a die (1–6)? A 6 does not divide by 5, so it is an unfair number. When that happens, drop it and roll again.
Concept
Picking 5 with a 1–6 die?
Set the winning number from the die value's remainder mod 5. (This example does not add 1 to the remainder — the remainder itself is the winning number, and assumes a remainder of 0 makes No. 5 the winning number.)
| Dice | ÷ 5 | Remainder | → winner |
|---|---|---|---|
| 1 | Quotient 0 | 1 | No. 1 |
| 2 | Quotient 0 | 2 | No. 2 |
| 3 | Quotient 0 | 3 | No. 3 |
| 4 | Quotient 0 | 4 | No. 4 |
| 5 | Quotient 1 | 0 | No. 5 |
| 6 | Quotient 1 | 1 | No. 1 (again!) |
A die goes up to 6 but there are 5 people. So a 6 points to No. 1 again → only No. 1 gets a double chance, which is unfair. So reject the 6 and roll again. (Remainder 0 is the last, No. 5.)
Experiment
Real draw simulation — roll it yourself
"Fair" rejects a 6 and rerolls. "Unfair" keeps the 6 as is. Roll many times and compare the bar heights.
1Choose what to do when a 6 comes up
2Roll the dice many times and check the results
Fair mode rejects the unfair number (6) and rerolls, so the bars stay even. Unfair mode gives the 6 to No. 1 too, so only No. 1 grows taller.
menu_bookReferences · Rejection sampling (discarding unfair numbers)
- von Neumann, J. (1951). Various Techniques Used in Connection with Random Digits. National Bureau of Standards, Applied Mathematics Series, 12, 36–38.
- Lemire, D. (2019). Fast Random Integer Generation in an Interval. ACM Transactions on Modeling and Computer Simulation, 29(1), Article 3.