April 11, 2008

Unbiased Coin Tossing

Given a biased coin, with probability of Heads equal to x. How to do unbiased coin tossing?
show

Try to find the expected number of coin toss that would be required to call heads or tails?
show

What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?
show

How can we improve on the expected number of coin tosses?
show

How much expected coin tosses are we doing in this case?
show

5 comments:

  1. I'm afraid the answer to expected number of coin tosses that would be required to call heads or tails has a little problem, it's not totally incorrect, but it's correctness is subject to interpretation.

    Basically let h means heads on the coin, and t mean tails. We call H if it is ht and T if th.

    Your answer will be correct if you are saying that the sequence 'hht' is inconclusive but 'hh ht' is a H ( i.e. if you neglect both the two earlier coin tosses)

    The reason is that in your formula, you are saying that, if the first two coin tosses are inconclusive, then we are starting from scratch, i.e. neglecting the 2nd coin toss, but the 2nd coin toss can be instrumental in us calling H or T

    i.e. if hht is H then the answer will differ, and I attempt it as follows ...

    case 1 ... first toss gives you h .... then expected number of tosses now to get t is 1/p(t) .. 1/(1-x) ...
    (since it is a geometrically distributed random variable)

    case2 ... first toss gives you t .... then expected number of tosses now to get h is 1/p(h) .. 1/x ...

    case1 occurs with probab p(h) ... and case2 with p(t) ...

    Therefore expected number of tosses p(h)[1+1/p(t)] + p(t)[1 + 1/p(h)]

    ReplyDelete
  2. Basically I mean, if we get 'hht' ... I will not discard the first two h's ... but the last two ht of hht will call a H

    ReplyDelete
  3. Afroz, that would be incorrect. Since coin is BIASED. Your technique leaves p(Head) different from p(Tail) thereby invalidating the requirement that we need to do UNBIASED coin tossing.

    ReplyDelete
  4. "What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?"

    Why not simply saying : (1 - 2x(1-x)) ^ (e/2) ??

    What is being suggested here is that we only consider cases where we have all of the tosses as HEAD or TAIL , while we can have :

    h,h t,t h,h t,t .....

    I mean in each experiment we can have both h or both t but not in all of the experiments !

    ReplyDelete
  5. @Arian

    The fourth question explains it.

    An intelligent strategy is to ALSO associate [h^2k t^2k] to heads and [t^2k h^2k] to tails.

    The only way you would then not stop before "e" is if we get h^e or t^e.

    ReplyDelete