## Answer: One More Coin-Flipping Game

problem

For the sake of brevity, I’m going to use a lot of intuition on this one, and I’m only going to focus on expectation values, even though the question mentioned full probability distributions. I checked my answers against a computer, though, so I guess they’re probably right.

Alice needs to get two consecutive heads to win the game. Suppose she’s got one, but then misses finishing the pattern by getting a tails. Then she has to start all over, waiting until she flips two heads.

On the other hand, suppose Bob has one heads, and needs a tails. He misses by getting heads. That’s not so bad, though, because he’s not starting over. Instead, he’s already half way through his pattern.

Bob is thus more likely to win this game.

Let’s find the expectation value of the number of times Bob must flip before he finishes. First he must get a heads. This takes, on average, two flips. Then he must flip until he gets a tails. This takes two more flips on average, so Bob’s expected number of flips is four.

Alice also expects two tosses to get heads. But once she gets heads, she’ll need a third toss. Half the time, that’s a heads and she’s done. However, half the time she fails and has to start over. So Alice expects to have to go through the whole rigmarole twice. It takes three tosses to go through once, so her expected number of tosses to finish the game is six.

The full probability distributions are more difficult to compute (for me), but a computer simulation tells me that Bob wins about 68% of the time.

To generalize to longer patterns, let’s denote a particular pattern with $n$ flips by $p_n$. Its expected number of flips to finish is $E(p_n)$. Then we’ll say that $p_{n-1}$ is the same pattern without the last flip. In order to finish the pattern $p_n$, you must first finish the pattern $p_{n-1}$. This takes $E(p_{n-1})$ flips on average. Then you’ll either finish the pattern on the next flip, or not.

If you do finish the pattern on the next flip, that’s great. There’s a $1/2$ chance of this, and the length would be $E(p_{n-1})+1$. On the other hand, if you fail by flipping the wrong thing on the last one, there are now two different scenarios. If the first and last sides of the pattern are the same and you failed to finish the pattern, then you must have flipped the opposite side as you started with, and so you’re starting completely over. You’ve done $E(p_{n-1})+1$ flips, and because each time you have a probability $1/2$ of finishing, you expect to go through this process twice. Your probability overall then is $2* \left[E(p_{n-1})+1 \right]$.

On the other hand, if you get almost all the way through but miss the last one and the pattern begins and ends on opposite sides, then when you start over you’re already at least one flip on the way. You might be even further along than that. For example, if you’re trying to get HHT, then you expect to flip $6$ times before getting HH, but once you do, you’ll finish very soon. Even if you miss your target of tails, you must have flipped heads. That means you still have a HH streak over your last two, and you can flip again. You expect to flip twice before finishing the sequence, so the expected number of flips for HHT is eight.

HTT is a different story. The answer works out the same, but the reason is different (as I see it). For HTT, you expect to flip four times to finish the HT pattern. Once you do, if you miss on the last one by getting heads when you wanted tails, you’ve got the first flip of your sequence, but you now need to score a TT. That takes six flips. So the total expected number of flips is $1/2*5 + 1/2*(5+6) = 8$.

The generalized formula is a bit more complicated than I really want to get into though, as far as I can see. Say you flip a coin 32 million times. Then any given 5-flip pattern should appear about one million times in the long sequence. However, some sequences overlap a lot, while others don’t. The ones that overlap a lot, like HHHTHHH, wind up giving further spacing than the ones that don’t overlap, as much, like HTHHTTT. If the patterns overlap, then sometimes the end of one pattern is close to the end of the next, and sometimes far away. Choosing a spot at random in the sequence, you’ll probably wind up in one of the stretches where the ends of the patterns are far away from each other, hence it’ll take a lot of flips to finish the sequence. On the other hand, if the sequences don’t overlap much, then the spread between where they end is pretty much even, and if I pick a spot at random, it’s likely to be a more moderate number of flips before I finish the sequence.

Sorry to be lame and not provide full answers.