## Thursday, November 24, 2016

Which takes fewer flips of a coin, getting two heads in a row, or getting a head followed by a tail? I'm talking about the average number of flips. It's of course possible to get lucky and hit two heads in the first two flips, or a head and a tail. But if you flipped a coin until you got HH or HT, and wrote down the number of flips, then did this say 10 times total, which one would come up faster, on average?

When this question was posed to me, I made the following argument: in both cases you have to flip a H, so there is no difference there. Once you get the first H, you are equally likely to flip a H or a T. The first would give you HH and the second would give you HT. Therefore, HH and HT must take the same number of flips, on average...right?

If that doesn't make sense to you, come up with your own answer, or try it out with a coin yourself. Then scroll down to find the real answer.

To find the average number of flips until HH appears, I started writing down all the ways you can get HH:

In 2 flips, the only way is HH, and there is a 1/4 chance of that.
In 3 flips, there is also only one way: THH. There's a 1/8 chance of that.
In 4 flips, TTHH and HTHH both work. Each of them has a 1/16 chance, but there are two ways, so the total probability of reaching HH in 4 flips is 2/16.
In 5 flips, TTTHH, THTHH and HTTHH; total probability of 3/32.
You can figure out the next two: for 6 flips it's 5/64 and for 7 flips it's 8/128.

Then I did the same thing for HT:

2 flips - one way, HT, 1/4 chance
3 flips - two ways. THT and HTH. 2/8 chance.
4 flips - TTHT, THHT, HHHT. 3/16 chance.

You can already see that there are more ways to get HT than HH. So it seems likely that it would take fewer flips on average to get HT than HH.  But what is the real answer?

The average number of flips will be the sum of the number of flips times the likelihood that number of flips gets you the desired result. Looking above at the flip sequences I listed for HH, $n$ flips has a probability of $F_{n-1}/2^n$ of getting you HH, where $F_k$ is the kth Fibonacci number. (Look back at the numerators in the HH probabilities. 1, 1, 2, 3, 5, 8...) That's the Fibonacci sequence, which is defined as starting 0, 1 and then each following number is the sum of the previous two numbers. I think it's really spooky that the Fibonacci sequence shows up here. So the average number of flips is $\sum_{n=2}^\infty \frac{n F_{n-1}}{2^n} = 6,$
So it takes 6 flips on average to get two heads in a row.

Looking at the probabilities for HT, the formula is $\sum_{n=2}^\infty \frac{n(n-1)}{2^n} = 4.$ It takes only 4 flips on average to get a head followed by a tail! As the mathematicians say, that's a counterintuitive result.

Exercise for the reader: Show that it takes exactly 2 flips on average to get one head.