# 20 Heads In a Row - What Are the Odds?

A couple of weeks back I took issue with a statement in the New York Times Magazine:

If you have a million coin flips, it’s almost certain that somewhere in those coin flips there will be 20 heads in a row. My blog post took the Times to task for printing what seemed to be an obviously bogus statement. Since a run of 20 heads is roughly a one-in-a-million occurence, a basic feel for probability should tell you that trying to do this a million times is not going to be a certainty - fairly far from it.

Naturally, I thought to back up my argument with some hard facts, and I came up with a calculation that showed that the chances of this happening were actually around 60%. Unfortunately, I made a pretty basic mistake in calculating the probability, as was demonstrated to me by correspondent Andy Langowitz. My intuition about the likelihood of success was on the money, but my estimate was a bit high.

The story of how I corrected my error in order to get the correct number, around 37.9%, is a good lesson in careful examination of probability rules, with a small detour into the land of the bignum.

#### Independent Probabilities

When trying to develop a formula like this one, it is often easier to work from the inverse. Instead of calculating how likely it is for 20 heads to occur at any point in the sequence of a million tosses, I thought to instead calculate the probability that it wouldn’t happen. We can then take that number and subtract it from one to get the desired result.

The chance of *n* heads in a row occurring is 1/2^{n}, so the inverse probability is
(2^{n}-1)/2^{n}. If we multiply that probability once for all 999,981 possible
occurences of a streak of 20 heads, it seemed to me that I would be in business. Doing this is a
simple enough calculation, and the result was the 60% figure. That figure felt like it was in the
ballpark to me, and I left it that.

Mr. Langowitz, however, was smart enough to actually test the theory on a smaller set of numbers. Let’s apply this theory to find out how likely we are to throw two heads in a row in four tries.

The chance of two heads in a row is 1/4, so my formula would give a result of 1 - (3/4)^{3},
or a result of 37/64 - a little better than 50% chance of it occuring. But probability is nothing
but the art of enumerating and counting, and we can do just that to check the result. The 16
equally possible outcome of four tosses are:

```
HHHH HHHT HHTH HHTT
HTHH HTHT HTTH HTTT
THHH THHT THTH THTT
TTHH TTHT TTTH TTTT
```

Look through those outcomes and see how many have two consecutive heads. It turns out to be exactly 8, meaning that my calculation of 37/64 is just flat wrong.

#### Locating the Mistake

My mistake is a pretty common one among probability neophytes. I assumed that probability at each step in the sequence was identical, because the sequences were completely independent. It’s easy enough to think that if you don’t examine problem carefully.

What actually happens is that when we examine the possibility of an unsuccessful run of heads at
toss *i*, we slightly bias the outcome at toss *i+1*. A demonstration will show
exactly how this happens.

For the sample problem of a sequence of two heads out of four tosses, we can first examine the chance of a negative outcome starting at toss 1. There are just four possible outcomes that have two tosses starting at position 1:

```
HH HT TH TT
```

And only one of these tosses yielded two heads in a row, so the probability of not seeing two heads after two tosses is 3/4.

But now when we look at the sequence of tosses starting at position two, we have to throw out the outcomes where we had two heads at toss one - we’ve already seen two heads, so we can’t continue flipping coins in those outcomes. So our universe of possible outcomes is now a bit different:

```
HTH HTT
THH THT
TTH TTT
```

Instead of eight outcomes, we have six. And if we look at the first toss seen in position two, instead of having an even distribution of heads and tails, you can see that sample is biased: only two have a head in position two, while four have tails. So the chances of not seeing two heads starting at position two increases to 5/6. Note that this change in probability occurs because we have selected only those outcomes without a streak of two heads at position one.

Likewise, when we look at the possible outcomes for streaks starting at position three, we get a different probability again. Because we have to throw out one sequence in the previous test, the universe of possible outcomes is now limited to:

```
HTHH HTHT
HTTH HTTT
THTH THTT
TTHH TTHT
TTTH TTTT
```

So now we have just ten possible outcomes, and two of those will produce the desired outcome, meaning the probability has changed to 4/5.

So what is the probability of all three possible positions not containing a streak?
That would be (3/4)*(5/6)*(4/5) which reduces nicely to 1/2, the correct answer.

#### Finding the General Solution

So let’s generalize the question at hand: what is the probability of seeing *k* consecutive
heads when a fair coin is tossed *n* times? The previous section showed that we can work it
out by hand for small numbers of tosses, but it should be clear that if are going to toss a coin
a million times, the universe of possible outcomes is going to get unwieldy. We need a general
description of the problem in order to solve it for any values of *k* and *n*.

For many probability problems, finding a solution is simply a way of figuring out how to count
things, and coin tosses indeed appear to be just such a problem. Let’s try to see if we can count
the number of times a sequence of *k* heads will appear at a given toss.

To start to work out the solution to the problem, I will set *k* to a value of
three - in other words, we will be trying to see what is the probability of seeing three
consecutive heads is at toss *i*, given that there have not been three heads at an
earlier toss. To calculate the probability, we need to know two things. First, we need to know
all the possible outcomes in our universe of samples at toss *i*. In the previous section,
with a value of *k*=2, we saw the the number of outcomes for tosses 1, 2, 3, and 4,
was 2, 4, 6, and 10.

After determining the number of outcomes, we then need to determine how many of those outcomes
were successes. If we defined success as being the number of outcomes in which a *k* heads
in a row appear at position *i*, the values from the previous section would
have been 0, 1, 1, 2.

#### Counting the Successes

I’ll start with the more difficult problem: counting the number of times *k* heads appear at
toss *i*. To start with, we have the degenerate cases where *i* is less than *k*.
In all of those tosses, we know that the number of successful outcomes is going to be zero,
because there have not been enough tosses to achieve success yet.

If we work our way forwards with the example of *k*=3, our first four tosses end up giving
us three sets of outcomes:

```
H T
HH HT
TH TT
HHH HHT
HTH HTT
THH THT
TTH TTT
HHTH HHTT
HTHH HTHT
HTTH HTTT
THHH THHT
THTH THTT
TTHH TTHT
TTTH TTTT
```

Note that when we get to toss 3, there is just one successful outcome. Likewise, in toss 4, there is just one successful outcome.

It may not be immediately obvious, but we can in fact always tell how many successes we will
achieve at toss *i+k* after we have enumerated all the possible outcomes at toss *i*.
The number is defined as the number of outcomes at toss *i* that end in a tail.

The logic behind this is straightforward: in order to have a success at position *i+k*,
we need to generate a sequence of *k* heads, starting at toss *i+1*. If we have an
outcome that currently ends in a tail, it will generate 2^*k* outcomes in the next *k*
tosses, and precisely one and only one of these will have *k* consecutive heads.
None of these outcomes will result in an sequence of *k* heads before toss *i+k*,
because they currently terminate in a tail, so all of the outcomes generated from that
outcome at position *i* will be included in the outcomes seen at toss *i+k*.

Likewise, none of the outcomes at position *i* that currently end in a head are going to be
able to contribute to a success at toss *i+k*. Any streak of *k* heads that follows a
terminating head at toss *i* will result in a run of *k* heads *before*
we reach toss *i+k*.

Looking at our outcomes for *k*=3, we can see that at toss 1 we have one outcome ending in a
tail, so at toss 4 we will have one success. At toss 2 we have two outcomes ending in a tail,
so at toss five we will have two successes. And we have the special case of toss 0 - we have one
sequence starting at toss 0 that generates a sequence of *k* heads at toss *k*.
Although there were no tails tossed at position 0, any sequence that starts there doesn’t
have any preceding heads tosses either, so it is as if there was a single outcome at toss 0 with a
value of tails.

So each toss that ends in a tail acts as the root of a successful outcome at a future position.
This is good information, but in order to turn this in to a formula we need to be able to compute
the number of outcomes ending in tails at toss *i* - we don’t want to have to enumerate all
the outcomes in order to get there. I’ll refer to these special outcomes as *anchors*,
as they form the anchor of a future outcome.

#### Counting the Anchors

The number of anchor outcomes at each position starts out as a nice number while *i* is less
than or equal to *k*: 2^*i*. But after toss *k*, successful outcomes start being
removed from the sample set and the formula no longer holds. For *k*=3, the anchor count
starting at toss1 is: 1, 2, 4, 7, 13, 24.

It turns out that the anchor at position *i* does more than just generate a success at
toss *i+k*. It is also responsible for generating new anchor outcomes at
tosses *i+1*, *i+2*, …, *i+k-1*.

Looking at an example for *k=3* should clarify this. Our lone anchor outcome at toss 1 is
the sequence `T`

. We know that this anchor will create a new successful outcome at toss 4: `THHH`

.
But it also creates new anchors at all intermediate tosses: `TT`

, `THT`

, and `THHT`

.

This observation holds true for the generation of all new anchors, and with a little work we can
turn this into a usable recurrence. If each anchor at toss *i* is going to create a new
anchor at tosses *i+1* through *i+k-1*, we can calculate the number of anchors at
toss *i* using this formula:

You might recognize this formula if we write it out for *k*=2:

```
anchors(i)=anchors(i-1) + anchors(i-2)
```

Yes, that is the Fibonacci sequence. For values of k higher than 2, the formula is the
n-step Fibonacci sequence.
The well-known Fibonacci sequence recursively adds the previous two values to get the current
value. The **n-step Fibonacci** sequence adds the previous *n* values in order to get
the current value. (For the rest of this article, the n-step Fibonacci number will be referred to
as fib_{n}(i).)

In the standard Fibonacci recurrence definition, we define a base value of fib(1) = 1, and
fib(x) = 0 for all x less than 1. Our anchor count is skewed by one, since our base value at
toss 0 is 1. As a result, the the anchor count at toss *i* is equal to
fib_{k}(*i+1*). And from our observation of the link between anchors and successful
outcomes, we can then observe that the number of successful outcomes at toss *i* is equal to
fib_{k}(*i+1-k*).

#### Counting the Outcomes

Knowing the number of successful outcomes at toss *i* only gets us halfway to knowing the
actual probability of seeing a sequence of *k* heads at that point. To get the full
probability, we need to know the number of outcomes as well.

Fortunately, this calculation is nearly trivial. In the previous section we saw that the number of
anchors at toss *i* is equal to fib_{k}(*i+1*). Each anchor at toss 1 and
greater is simply a sequence of tosses that ends in a tail. And for every sequence ending in a
tail, there is a corresponding sequence that is identical except for one key change: it ends in a
head instead of a tail. So the number of outcomes at toss *i* is twice the number of anchors,
or 2*fib_{k}(*i+1*).

Now that we have those numbers, we can finally crank out the probabilities of a streak
of *k* heads appearing at all possible tosses without having to painstakingly enumerate all
those sequences of heads and tails. The figure below shows some of the probabilities for tosses
starting at 1 for streaks of 2, 3, and 4 heads. It is an excellent exercise to walk through the
enumeration process in order to double check the figures - I encourage you to give it a try.

#### The Absence of a Streak

Now that we can compute the probability of seeing a streak of *k* heads at toss *i*,
we need to do just a bit more work to see the what the odds are of seeing that streak at any
time in a sequence of *n* tosses. To get there, we need one more piece of information:
the probability of *not* seeing a streak of *k* heads at toss *i* - in other words,
the chances of a negative outcome.

It’s pretty easy to calculate that number - simply subtract the number of successful outcomes
from the total number of outcomes. The sample sequences for values of *k* corresponding to
2, 3, and 4 are shown here:

In order to make the final probability calculation a bit easier, I’m going to derive a value for
the count of failures that simplifies future calculations. In the first line of the figure below
we have the basic calculation - the number of failures at toss *i* is equal to the total
number of outcomes less the number of successes. Both of those two values used to derive the
failure count can be expressed in terms of an n-step Fibonacci number, and that is shown on the
next line.

In the third line of the figure I simply break out the value first term of the equation into its
two component parts. Now, in the next line, I expand the value of fib_{k}(*i+1*)
into its component parts, using the definition of the Fibonacci sequence. I keep that grouped in
parentheses to make it clear that the new terms are the result of the expansion. Just as an
example, if we were doing this expansion for a value of *k* equal to 3, we would expand
fib_{3}(*i+1*) into the sum of fib_{3}(*i*),
fib_{3}(*i-1*), and fib_{3}(*i-2*), using the identity of the
n-step Fibonacci sequence.

Note that in line 3, the last term of the expanded Fibonacci sequence in parentheses is canceled
by the last term overall, which was the number of successful outcomes. When we remove those two
elements from the equation, line 5 has simplified into the identity of fib_{k}(i+2).
So we now have a reasonable number we can use to determine the count of failures at a given toss.

#### Put it All Together

With all these formulas in hand, we have the tools to determine the final probability we’ve been
working towards: the probability that a sequence of *k* heads will appear in a sequence of
*n* tosses. To do this, we calculate the cumulative probability that the event does not
occur, and subtract that value from 1. The result will be the answer to the question.

The first equation below shows the general approach we take to this problem - multiplying the
probability of failure at each toss. Once we plug in the actual formula for the failure count at
each point, and the formula for the total number of outcomes, we see that most of the terms cancel
out. We are left with fib_{k}(*n+2*) on top, and 2^{n} on the bottom.
And that is the final formula that provides an answer to the question.

Returning to the original supposition in the New York Times, all we need to do is calculate
fib_{20}(1,000,002) and then divide it by 2^{1,000,000}.

Unfortunately, my calculator is not really up to this. Even a desktop calculator that could
handle arbitrary precision math won’t normally have a fib_{k} button.

If I had a copy of Mathematica, and knew how to use it, I think I could solve this with just a few lines of input. But I don’t, so I coded up a short solution in Java.

Java has two classes that enable me to solve this problem in relatively easy fashion: java.math.BigInteger and java.math.BigDecimal. BigInteger performs simple integer calculations with arbitrary precision, and BigDecimal supports floating point math.

My simple app, contained in
Flipper.java,
uses BigInteger to calculate fib_{k}(n+2) and 2^{n}, then uses BigDecimal to
divide the two numbers and subtract the result from 1. Despite fact that the two intermediate
results are over 300,000 digits each, the program ran in a very reasonable amount of time,
less than an hour. (Optimization of this program would be a very interesting exercise.)

The output of the program is shown here:

```
fib(20,1000002) = 614579313398524367786474463596 (301000 digits elided)
2^1000000 = 99006562292958982506979236163 (301000 digits elided)
Div = 0.379253961388950068663971868 (999980 digits elided)
```

So at last, we know the correct result. If you flip a coin a million times, you have a 38% chance of seeing 20 heads in a row. A long way from the certainty claimed by the New York Times, and a bit off from my initial 60% value.

#### Postscript

Working out the details of this problem was a very enjoyable piece of math. When I first started in on the problem, I hoped I would be able to find a reference that simply told me how to calculate the number, but I had no luck. As I worked through the problem, I ran into the existence of the n-step Fibonacci numbers, which I had never heard of. Once I found the reference to them on the Wolfram Alpha page (linked above), I saw that the page had a terse note describing this problem, but with no details. With luck the next person trying to understand this problem will be able to make sense of it by reading this page.