What Is the Probability of Equal Heads and Tails After 8 Coin Tosses?

[Yagoda]

Homework Statement

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.

Homework Equations

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?

 

[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.

 

[haruspex]

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?

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?

 

[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.

 

[haruspex]

That numerical calculation is still a mystery to me.

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})$