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.
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/2n, so the inverse probability is (2n-1)/2n. 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 MistakeMy 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:
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:
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 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 the probability of seeing three consecutive heads is at toss i. 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:
Note that when we get to toss 3, there is just one successful outcome. Likewise, in toss 4, there is just one successful outcome.
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
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 AnchorsThe 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:
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:
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 fibn(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 fibk(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 fibk(i+1-k).
Counting the OutcomesKnowing 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 fibk(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*fibk(i+1).
The Absence of a StreakNow 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 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 fibk(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 fib3(i+1) into the sum of fib3(i), fib3(i-1), and fib3(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 fibk(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 TogetherWith 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 fibk(n+2) on top, and 2n on the bottom. And that is the final formula that provides an answer to the question.
Unfortunately, my calculator is not really up to this. Even a desktop calculator that could handle arbitrary precision math won't normally have a fibk 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 fibk(n+2) and 2n, 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.
PostscriptWorking 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.