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.
(In reply to
"Inflate and Gamble" algorithm by Larry)
I like the "inflate and gamble" approach, but I think there's some refinement needed.
Suppose N = 9. Then I can certainly add enough people to get to N = 16. k = 4 and d = 7, so the expected flips is 4*2^4 / (2^4 - 7) = 64 / 9 ~= 7.1
But suppose instead I flip 6 at a time, creating 64 different possibilities. I assign them in groups of 7 to each person, which uses 63, and I repeat the process if I flipped a "64".
Now k = 6 and d = 1, and the expected flips is 6*2^6 / (2^6 - 1) = 384/63 ~= 6.1
So flipping more to begin with (6 at a time vs 4 at a time) has actually reduced the expected number of flips.
This approach doesn't always yield an improvement. For N=5, for example, we can flip in 3's and we'll repeat 3/8 of the time, or we can flip in 5's and repeat 1/16 of the time, but that's not a big enough improvement -- the former gives an expected flips of 4.8 vs ~5.3 for the latter.
So while this algorithm absolutely lets you choose fairly among N people, I don't have a way to compute the minimum expected number of flips, or to compute the optimal number of imaginary friends to add.
|
|
Posted by Paul
on 2024-07-02 13:30:21 |
re:
