Given a biased coin, with probability of Heads equal to x. How to do unbiased coin tossing?
show
Lets define an event, E as tossing the biased coin twice. The possible outcomes with probabilities is as follows
P(h,h) = x^2
P(h,t) = x(1-x)
P(t,h) = x(1-x)
P(t,t) = (1-x)^2
The event h,t or t,h are equi-likely, without any bias we can call that if Event h,t occurs it means head, t,h means tails but if h,h or t,t occurs we repeat the experiment.
Try to find the expected number of coin toss that would be required to call heads or tails?
show
Let expected coin toss be e.
Probability that we get outcome in 1st event is 2x(1-x)
Total number of coin toss would be 2
Probability that we get no outcome in 1st event is [1 - 2x(1-x)]
Total number of coin toss would be 2 + e (we wasted 2 coin toss and still we expect e)
==> e = 2 * 2x(1-x) + (2+e) * [1 - 2x(1-x)]
==> e = 4x(1-x) + 2 - 4x(1-x) + e - 2ex(1-x)
==> e = 1/ [x(1-x)]
so for x = 1/2, e = 4
for x=2/3, e = 4.5
for x=1, e = INF (as expected, because all we get is chain of h h h h h)
What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?
show
p = prob of e heads + prob of e tail
==> p = x^e + (1-x)^e
To find a bound on this p in polynomial terms can be done by using binomial expansion and
Newtonian series is out of the scope of this blog. But some number crunching is.
For x = 1/2, e = 4, p = 0.125
For x = 2/3, e = 4.5, p = 0.168
For x = 3/4, e = 5.33, p = 0.216
For x = 0.99, e = 101, p = 0.362
This tells us that probability that outcome comes is quite good even for high coin biases.
How can we improve on the expected number of coin tosses?
show
In above method, we say that HT or TH terminates experiment. and continue the experiment a fresh when the outcome is HH or TT.
We can further combine outcome of two such events to increase the probability of outcome e.g. say HH TT => heads and TT HH means tails.
How much expected coin tosses are we doing in this case?
show
try
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.
ReplyDeleteBasically 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)]
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
ReplyDeleteAfroz, 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"What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?"
ReplyDeleteWhy 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 !
@Arian
ReplyDeleteThe 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.