Suppose you have one fair coin, that is, a coin that comes up heads half the time and tails half the time.
Show how to use this coin to choose fairly among N people. Solutions using the fewest coin tosses are preferred.
My refinement to “inflate and gamble” is to assign people using binary starting at 0, flip coin 1 at a time, and stop flipping and start over as soon as it is clear that the flips do not correspond to a person. This is always better than straight “inflate and flip” except for N = 2^k or 2^k - 1, when it is the same.
It is particularly good for 2^k + 1 and for 2^k + 2
Consider N = 65.
Flipping coins will select a person 65/2^7 = 65/128 times.
But when it fails to select a person, we can usually stop before flipping 7 times.
32/128 times we come up 2 heads and can stop after 2 flips.
16/128 times we flip HTH and stop after 3 flips.
8/128 times we flip HTTH and stop after 4 flips.
4/128 times we flip HTTTH and stop after 5 flips.
2/128 times we flip HTTTTH and stop after 6 flips.
1/128 times we flip 7 times only to find out that we have failed with HTTTTTH.
The average number if flips if we fail once is only 177/63 = 2.8095
The total number of expected flips is (177/63)*((128/65)-1) + 7=
(177/63)*(63/65) + 7 = 177/65 + 7 = 9.7231
This is better than the best overinflation approach.
Factoring 65 = 5*13 might be even better, but I have not tried that.
Edited on July 3, 2024, 11:38 am
A better N = 65
