A Coin Flipping Question

1. May 17, 2014

Yagoda

1. The problem statement, all variables and given/known data

Toss a fair coin independently 100 times. Let X > 0 be the number of times the coin must be tossed until the number of observed heads equals the number of observed tails. (And let X=100 if this never happens). Find the probability that X=8.

2. Relevant equations

3. The attempt at a solution
In order for X to be 8 we need there to be exactly 4 heads and 4 tails after the 8th flip. But we also need there to not be equal heads and tails at any point before this, which could occur after the 2nd, 4th and 6th flips. Thus we cannot have sequences beginning with TH, HT, HHTT, TTHH, etc. I tried enumerating all of these types of sequences but I couldn't come up with a systematic way of figuring them out.

This problem is from an old exam and in the solution that came with it the answer given is simply $\frac{1}{2}\times\frac12\times\frac12\times\frac14 + \frac12 \times \frac14 \times \frac{1}{16} = \frac{5}{128},$ with no other explanation provided. I can't really make sense of these numbers or figure out how they got it. Am I just really overthinking it?

2. May 17, 2014

verty

Can you show some working out for this problem? You've shown some intuition about what is required but it's at a very nascent stage.

3. May 17, 2014

haruspex

I'm not sure how they arrived at that either, but I find this problem quite easy done graphically.
You have to get from (0,0) to (4,4) without going through (1,1) etc. Without loss of generality, the first move is to (0,1). What is the last move, etc?

4. May 17, 2014

Yagoda

Thanks for providing a nice, intuitive approach. I don't think I would be clever enough to come up with that under the time pressure of an exam.
That numerical calculation is still a mystery to me.

5. May 17, 2014

haruspex

Here's a possibility, matching it to the graphical view:
Without loss of generality, first move is to (0, 1), so last needs to be from (3,4), with prob $\frac12$.
Clearly the second step must be to (0,2), and the step before (3,4) must be from (2,4), each with prob $\frac12$.
There are two allowed sets of routes from (0,2) to (2,4) - via (0,4) or via (1,3).
Via (1,3) we have $\frac12$ for (0,2) to (1,3), and $\frac12$ for (1,3) to (2,4), giving $\frac14$ altogether.
Via (0,4), we have $\frac1{16}$.
Putting all that together gives $\frac12\frac12\frac12(\frac14+\frac1{16})$