Unbiased Coin Puzzle
Unbiased coin puzzle
A little variation to the Biased coin puzzle.
You and your rival are competing for the same girl, and decide to settle it with a coin toss. Your rival has known the girl longer than you have, so you agree that it is fair for him to have a chance of winning equal to P, where P > 0.5. However, you only have a fair coin.
How can you conduct this contest such that the biased probability is manifested? What is the average number of coin flips needed to determine a winner?
—
RSS - Posts
This comment has been removed by a blog administrator.
This comment has been removed by the author.
Let p be rounded off to 2 places of decimal(assumed).
Throw the coin ceil(log(100) base2) times, i.e. 7 times.
(7 coz, its nearer to 100, so p can very well get converted to a 2-digit number)
Each outcome is equiprobable, hence let any p’ * 128 of outcomes belong to opponent and rest belong to u.
Throw the coin 7 times, and accumulate the result. If at the end, result belongs to the set of opponent, he wins, else you win.
e.g.
p=0.6, p’ =128*0.6=76.8~77,
So, let first 77 outcomes (0-76) belong to opponent and 77-127 to u. Let H be 1 and T be 0. I
f coin throw results in HTTHTTH (last throw being the MSB) = 1001001 = 64+8+1 = 73
As 73 belongs to the range of opponent, he wins.
or we can toss the coin for some 10 times (say) . .if my rival gets it more than p fractions time he wins, if he gets less than P times, I win 🙂