Equal Heads and Tails: The Expected Number of Tosses (Coin Puzzle)
Source: Posted by chera (Gaurav Sinha, IITK 1996 Graduate, Indian Revenue Service) in comments on Consecutive Heads Problem
Problem:
Suppose you have a fair coin and you toss it until you have got equal number of heads and tails. What is the expected number of tosses? Note that probability that the game stops in odd number of tosses is 0. The probability that the game stops in 2 tosses = 0.5
Solution:
Different solutions posted by Kalyan Parhi (EE IITB Alumnus), Abhash, Siva, Gaurav Sinha (CSE IITK 1996 Alumnus, Indian Revenue Service), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer) in comments!
Problem:
Suppose you have a fair coin and you toss it until you have got equal number of heads and tails. What is the expected number of tosses? Note that probability that the game stops in odd number of tosses is 0. The probability that the game stops in 2 tosses = 0.5
Solution:
Different solutions posted by Kalyan Parhi (EE IITB Alumnus), Abhash, Siva, Gaurav Sinha (CSE IITK 1996 Alumnus, Indian Revenue Service), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer) in comments!
E(X)=sum_(1 to inf) binomial(2n,n)*2^(-2n).
ReplyDeletenow as n->inf by stirling approximation T_n->n^(-.5)
which, by cauchy convergence criterion, is divergent.
I dunno what's wrong.
sorry about previous argument..In E(X) nth term T_n has probabilty = p_n = q_(2n-2)-q_2n..where q_2n=binomial(2n,n)*2^(-2n)..solving E(X)=2*p_1+4*p_2+...=2(1-q_2)+4(q_2-q_4)+...=2(1+q_2+q_4...)..now we can show as from previous comment that this diverges..so still clueless..:(
ReplyDeleteThe expected number diverges for me too.
ReplyDeleteFor all the situations where the absolute difference between the number of heads and tails is same the expected number of tosses required to reach the situation of equal number of heads and tails is same. Also, if the current difference is 'd' then with equal probability the difference may increase or decrease after the next toss. Let E(d) be the expected number of tosses required to get equal number of heads and tails when the current difference between their counts is d. So, E(d) = 1 + 0.5 * E(d-1) + E(d+1). Also, E = 1 + E(1). and E(0) = 0. Solving this, E = i + (1/i)*E(i). Since for any i E(i) will be positive. The result diverges.
This is a problem involving catalan numbers..
ReplyDeleteE(x) = 2*sum 2n*C(2n-2)* 1/2^2n which is indeed divergent.
The reason is that the we are dealing with a random walk. There is a good chance (1/2) in this case that the number of heads are never equal to the number of tails. The proof is fairly trivial using recursion.
For a general coin which is not fair, the probability that the number of heads is ever equal to the number of tails is min(p,1-p). again as I said the proof is trivial by recursion.
@kalyan.. Yes, it diverges. But I think T_n->n^(0.5) and not n^(-0.5). Please check if I am wrong!
ReplyDelete@abhash.. very interesting approach..
Let E(d) be the expected number of tosses required to get equal number of heads and tails when the current difference between their counts is d.
E(d)= 0.5(1+E(d+1)) + 0.5(1+E(d-1)) for d>1
i.e.
E(d) = 1 + 0.5*(E(d-1)+E(d+1)) for d>1
i.e.
E(d-1)=2*E(d)-E(d+1)-1 for d>1
and E(1) = 1+0.5*E(2)
E(0)=0
We need to find the value of E: E=0.5(1+E(1))*2=1+E(1)
@abhash: How did you solve this recurrence?
@Siva.. Please check kalyan's solution! Your expression is not correct! Your argument, though is correct!
@kalyan.. Sorry. Got my formula for stirling approximation wrong. You are correct! It diverges as T_n->n^(-.5)
ReplyDeletethe probability that eventually H=T is one,i.e. almost certain.
ReplyDeleteand in a general case of biased coin, where the probability of head is p, probability that eventually H=T is 2*min(p,1-p).
Proof is available at math.stackexchange.com/questions/17999/1d-random-walk-probability-to-go-back-to-origin.
@chera.. Thanks a ton!
ReplyDelete@Siva.. I take my statement about your comment back. Your probability is not correct, and hence your solution (both the calculation and the approach) is wrong!
Yes of course.. I take my comment back... I missed a factor of 2.
ReplyDeleteso instead of 2*min(p,1-p) I wrote min(p,1-p) which led to to the wrong answer. I wish I could edit my post.
a solution for finding probability that eventually heads=tails in case of a biased coin.
ReplyDeleteconsider a random walk with probability p of moving right and 1-p of moving left. u start at origin O. assume wlog that p<1/2. suppose the probability that eventually u return to origin is x. there are two possibilities:
Event E1: first step is towards right. In this case,we can assume that certainly u will return to origin as p<1/2. so probability(E1)=p.
Event E2: first step is towards left to point A, and u return to origin O after crossing A n times.
probability (E2 for a fixed n)=(1-p)(p)(x-p)^n.
hence x= probability(E1)+probability (E2)
i.e. x=p+ sigma (1-p)(p)(x-p)^n.
where sigma is from n=0 to infinity.
on summation of geometric series and simplification, we get quadratic equation
(x-1)(x-2p)=0.
so x=2p ignoring x=1.
as we assumed p<1/2,
general solution is x= 2 min(p,1-p)
Edit to my first post:
ReplyDeleteThis is a problem involving catalan numbers..(http://en.wikipedia.org/wiki/Catalan_number)
I think my earlier expression for expectation is most probably correct.
earlier poster makes no mention of the expectation which is what the question asks for.
This expectation is infinite and can also be explained as a direct consequence of the optional stopping theorem
(http://en.wikipedia.org/wiki/Optional_stopping_theorem)
@pratik, To solve the recurrence find the value of E(d) in terms of the E(d+1). It turns out to be
ReplyDeleteE(d) = d + d/(d+1) * E(d+1)
This can be done using induction. If we plugin this to find the value of E we get,
E = d + 1/d * E(d)
This result is true for any d > 1 and can be proved via induction.
A (standard) generating function approach. Let P(x) = sum_{n=0}^{\infty} p_n x^n where p_n is the probability that the walk returns to origin in 2n steps. note that p_0 = 1. Similarly, let Q(x) = sum_0^{\infty} q_n x^n where q_n is the probability that the walk returns to the origin for the first time in 2n steps. Note that q_0 = 0. Then,
ReplyDeletep_n = \sum_{k=1}^{n} q_k p_{n-k}
The convolution suggests going to the generating function domain where this equation becomes P(x) - 1 = P(x)Q(x) or Q(x) = 1-(1/P(x)). Its easy to see that p_n = binomial(2n,n)(pq)^n. The generating function for the central binomial coefficient is 1/sqrt(1-4x). So Q(x) becomes 1-sqrt(1-4pqx). Q(1) gives the probability of return at some point to the origin and can be seen to equal 1-|p-q|. So probability of the walk escaping to infinity is |p-q|. If the walk isn't symmetric, then immediately the expected time of first return in infinite. If p=q, the expected time of first return is the derivative of 1-\sqrt{1-x} at x=1 which is again infinite. By extracting coefficients out of Q(x) using binomial series, we can compute q_n as well.
The probability that if we had 2k trials, we'll have equal heads and tails:
ReplyDelete\binomial(2k,k)*2^(-2k)
Therefore, expected value is
\sum_{K=1}^{K=\infty} 2k*\binomial(2k,k)*2^(-2k)
@Sumit, we also have to ensure that in first 2r trials H never equals T, where r<k.
ReplyDeleteIf there are 2k trials, total number of ways will be 2C(k-1) where C(n)= binomial(2n,n)/(n+1) is well known as catalan number.
@chera , How did you get the total number of ways for 2k trials ?
DeleteThis is just a random walk, identical problem in 50 challenging problems in probability.
ReplyDeleteNo problem - and the corrected value 2*min(p, 1-p) is indeed the probability of ever returning to equality for a biased coin. (Blogger comments cannot be edited, unfortunately - the correction trail stays visible, which is its own virtue.) (replied using AI)
ReplyDeleteThe right framework, and it lands on the known answer. For p < 1/2: after a first step right you are at +1 with negative drift, so return to 0 is certain; after a first step left to -1, hitting 0 requires climbing against the drift, with probability p/(1-p). Total: p*1 + (1-p)*(p/(1-p)) = 2p = 2*min(p, 1-p). Your crossing-count decomposition is the long way to the same place. (replied using AI)
ReplyDeleteYes - Catalan numbers are exactly the right object here: the probability the game first ends at toss 2k is 2*C(k-1)/4^k where C is Catalan, and the expected stopping time sum diverges (terms decay like k^(-1/2)... precisely, the first-return tail decays as k^(-1/2), so the mean is infinite). The optional-stopping viewpoint is a nice companion explanation. (replied using AI)
ReplyDeleteNice - and the punchline is worth stating explicitly: E(d) = d + (d/(d+1))E(d+1) iterated downward gives E(1) = d + (1/d)E(d) for EVERY d, i.e. E(d) = d*(E(1) - d). If E(1) were finite, the right side would go negative for large d, which is absurd for an expectation. So E(1) = infinity - a proof that the expected time is infinite straight from the recurrence. (replied using AI)
ReplyDeleteThe first-return condition is missing: binomial(2k,k)/4^k is the probability of being tied at time 2k, but the game stops at the FIRST tie, so you must count paths that never tied before - that is where the Catalan factor comes in (see chera's comment below). Also, as written your sum diverges for a different reason: 2k*binomial(2k,k)/4^k grows like sqrt(k), which is another signal the terms are not the right probabilities. (replied using AI)
ReplyDeleteCorrect - the first-return paths to 0 at time 2k are counted by 2*C(k-1): pick the sign of the first step (2 ways), and the middle 2k-2 steps form a Dyck path of semilength k-1. (replied using AI)
ReplyDeleteExpanding chera's count: suppose the first step is heads (double at the end for tails). To first return to equality at toss 2k, the walk must stay strictly above 0 for the middle 2k-2 tosses - i.e. tosses 2 through 2k-1 form a path of length 2k-2 from 0 to 0 never dipping below 0. Those are Dyck paths of semilength k-1, counted by the Catalan number C(k-1) = binomial(2k-2, k-1)/k. Times 2 for the first-step choice: 2*C(k-1) paths out of 4^k. (replied using AI)
ReplyDelete