Colin Fraser

Here’s the problem: given n coin flips, what’s the probability that you never see two heads in a row? This seems sort of like it ought to be easy to figure out, but if you try, it’s harder than it seems. The answer ends up being extremely surprising.

To solve it, we would basically need a way to count the number of sequences of T’s and H’s of length n that do not contain the string HH. To save some space and help avoid confusion, let’s give these sequences a name. I’ll call them c-sequences—c for “coin”. So henceforth in this blogpost, a c-sequence is a string consisting of nothing that is not an H or a T, and that does not contain the string HH. Then, to get the probability of never seeing HH in a sequence of n coin flips, we would just divide the number of c-sequences of length n by the total number of sequences of H’s and T’s of length n. So for instance if n=3 then we can just count them. All the sequences of length 3 are

1. HHH
2. HHT
3. HTH
4. HTT
5. THH
6. THT
7. TTH
8. TTT

Of those, 3, 4, 6, 7 and 8 are c-sequences. So the probability of flipping a coin 3 times and not getting HH ever is 5/8.

But as n grows, this becomes a really impractical way to do this. If n is, say, 30, then there are 1073741824 total sequences of H’s and T’s. No one wants to list those out and count the ones that don’t contain HH.

Luckily there ends up being a better way, and it’s really cool.

What we would like to have is a function f(n) which gives the number of c-sequences of length n. So as we saw above, f(3)=5, since there are five c-sequences of length 3. Once we figure out how to make f, the answer is easy: it’s just

since there are always 2^n total sequences of length n.

So we’ve reduced the problem to just finding a nice way to construct f(n). That’s where the beautiful part comes in.

We can start constructing f by defining f(0) and f(1). These are special cases since there aren’t any strings HH in the sequences of length 0 or the sequences of length 1 at all, since you need at least two flips to get two heads. I’ll start with f(1) since it makes more sense probably. There are two sequences of length 1:

1. H
2. T

Both are c-sequences since neither contain HH, so we define f(1)=2. Now f(0) is a little weirder—how many sequences of length 0 are there which do not contain an HH? You might be tempted to say 0, since there aren’t any sequences of H’s and T’s at all of length 0. You wouldn’t be wrong per se, but there’s another possible answer. We could also say that there is exactly one such sequence:

This is called the empty sequence, and it’s a perfectly good sequence that most mathematicians count as a sequence. It doesn’t contain anything that’s not an H or a T, so we can legally include it in the set of sequences of H’s and T’s, and it doesn’t include the string HH, so it’s a c-sequence (you might have thought that the way that I defined a c-sequence was awkwardly wordy—this is why, because that allows for the empty sequence to be a c-sequence). So I’m going to define f(0)=1, as there is one c-sequence of length 0: the empty sequence.

Now comes the really cool part. Think about all the c-sequences of length n where n>1. Any such sequence either ends with H or T. If it with H, then the second to last letter must be T—otherwise the sequence would contain an HH at the end, disqualifying it from being a c-sequence. So the list of c-sequences of length n that end with H looks something like this:

1. …HTHTTH
2. …THTTTH
3. …TTHTTH 
4. and so on…

So you can see that every c-sequence of length n ending in H is just a c-sequence of length n-2 with a TH tacked onto the end. In other words, if the above is a list of every c-sequence of length n that ends with H, if we just chop off the TH at the end, then it’s a list of every c-sequence of length n-2. So the number of c-sequences of length n ending with an H is the same as the total number of c-sequences of length n-2.

We can use the same kind of reasoning to look at the c-sequences of length n that end in T. The list of those looks something like this:

1. …HTTTTT
2. …HTHTHT
3. …THTHTT
4. and so on…

So the list of c-sequences of length n which end in a T is exactly the same as the list of all c-sequences of length n-1, but just tacking a T onto the end of each one. So the number of n-length c-sequences ending in T is the same as the number of n-1 c-sequences.

So we’ve just counted all the c-sequences of length n: it’s equal to the number of n-length c-sequences ending in H plus the number of n-length c-sequences ending in T, which is equal to the total number of n-2 length c-sequences plus the total number of n-1 length c-sequences.

In other words, for n>1, f(n)=f(n-2)+f(n-1), which means we can now completely define our function f(n): f(0)=1, f(1)=2, and for n>1, f(n)=f(n-2)+f(n-1). 

What’s so cool about that? Well it’s cool in its own right, since we are defining a function in terms of itself. But what makes it even cooler is that that is exactly the world-famous and universally revered Fibonacci sequence—well, almost anyway. Our function f(n) gives the n+2nd Fibonacci number.

So if we let F(n) represent the nth Fibonacci number, then we get a beautiful solution to the original problem: the probability of never seeing two heads in a row in n coin flips is given by:

Incidentally, since I mentioned 30 coin flips above, Wolfram Alpha gives about 0.002 as the probability of never seeing two heads in a row in 30 flips.

Well I thought it was cool anyway.

Inspired, by the way, by a discussion on /r/math.