Sunday, June 22, 2008

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?
---

4 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. 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.

    ReplyDelete
  4. 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 :)

    ReplyDelete

Subscribe via email

Enter your email address:

Delivered by FeedBurner