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.

## 25 users commented in " 20 Heads In a Row – What Are the Odds? "

Follow-up comment rss or Leave a TrackbackI searched for other solutions on the net. You are the only one I found with an actual method and explanation, and an actual result!

Congratulations

jimkurly@yahoo.ca

Hi Marc! Nice post. Unfortunately, you often find ppl telling you that the p to get a head or a tail would be 0.5 no matter how many heads you got before. This post clearly shows it’s obviously not because p changes with hypothesis (you could have a million coin flips or just a couple of them).

By the way, since you’ve mentioned Mathematica, I think this article would be good to mention. I especially like Saint Petersburg paradox because it shows that “It is misleading to consider the payoff without taking into account the amount lost on previous bets”.

On the other hand, the expected number of tosses required to get 20 heads in a row is 2^21 – 2 = 2097150, while the expected number of tosses required to get 20 heads OR 20 tails in a row is half that which is 2^20 – 1 = 1048575, which is close to a million. Maybe the New York Times saw that number in a book somewhere and misunderstood the concept of expectation in statistics.

http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics#What.27s_the_probability_of_getting_twenty_heads_in_a_row_if_you_flip_a_coin_one_million_times.3F

You can also evaluate this using generating functions. You then find that one minus the probability is:

Sum over lambda of (lambda/2)^N (lambda^20 – 1)* (21 lambda^20 – 40 lambda^19)^(-1)

where the summation is over the zeros of the polynomial:

z^21 – 2 z^20 + 1 = 0

excluding the zero at z = 1. Then the answer is dominated by the zero closest to 2, for N = 10^6, you get the first few hundred thousand decimal digits from that root only.

I explain this on the Wiki-page Bo Jacobi linked to above.

#Count:

Thanks for the enlightenment. I have to admit that while I am vaguely aware of this technique, I have no experience with it. I will endeavor to study the reference.

- Mark

Hi! how do you count 1 million coin flips, say i would play 100 flips today then 140 next day and so on aprox. 10000 days. Would that count as 1 million flips, would the results be the same ?

Thx.

@james:

yes.

thx.

By the way, 1/4 is the probability for exactly 2 heads in a row, while you are looking for at least 2 heads in a row in 4 trials.

[...] [3] http://marknelson.us/2011/01/17/20-heads-in-a-row-what-are-the-odds/ [...]

Hi Mark

Very interesting article, it was brought to attention by a friend, in an attempt to resolve a pub argument. However, the argument rages on…

I have two questions…

1) Where you say “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”… why can’t you continue flipping coins?

By stopping flipping after HH, you have taken the outcomes HHTT, HHTH, HHHT and HHHH, and counted them all as one outcome haven’t you?

Similarly, The Times article didn’t say anything about stopping when you get your streak of 20 heads, it said you toss the coin million times. Surely this means there are 2↑1,000,000 outcomes?

Your maths is clearly way more advanced than mine, so I’m sure your answer is right, I’m just struggling to understand why.

2)regarding this comment “you often find ppl telling you that the p to get a head or a tail would be 0.5 no matter how many heads you got before. This post clearly shows it’s obviously not because p changes with hypothesis”

… this is a misunderstanding isn’t it? p(heads)=0.5 and p(tails)=0.5 for any throw?

Well you can keep flipping coins, but there isn’t much point – you’ve already reached the outcome.

Deciding how to count things is what it’s all about. In this case, I’m counting the number of occurrence in which I

don’tsee two heads in a row. So I could keep flipping after HH, but there wouldn’t be any point. HHT doesn’t count, HHH doesn’t count, HHHT, doesn’t count, etc.The independent probability on any toss with a fair coin is always 0.5, no matter what the history is. If we stop believing that, the whole of civilization crumbles around us.

- Mark

IF I was too attempt to figure out the probability of say 9 consecutive heads in 1000, or say 2000 flips. Putting it in the formula would be easy enough. Problem is I don’t understand java at all. Is there another way around this problem?

You can enter the numbers in mathematica and get good results prety quickly.

- Mark

Hi Mark,

One simple way to check your results is to simulate the coin flips a number of times and see if the results are similar. For fun, I’ve done it in Java — it’s only about 45 lines of code — and I’m getting results that agree nicely with your final result. I had to be careful with the random number generator, though — using java.util.Random.nextInt() didn’t work, and never produced a run of 20 heads in a row. However, using Random.nextInt(99999999) produced a reasonable result, as did java.security.SecureRandom.nextInt(), although this is far slower. Averaging over 10,000 runs, I get results within a percent or two of your figure. Yes, that’s 10 billion random numbers generated in a little over 2 minutes in a single thread on a Core i7 processor.

Cheers!

Jeff

I tried entering your equation in as 1- (Fibonacci[20, 1000002]/2^1000000). Mathmatica gave me a ton of numbers that didn’t make sense lol. I don’t reallly know how to use this program though. I think Im close?? Do you have to subscript the 20 for k as heads? If so I wouldn’t know how to do that. Any suggestions?

Hi,

Great derivation!! I was wondering if you could help me and my co-workers out? We are wondering how you would obtain the answer to what is the probability that 20 in a row happens only twice? Generally what are the odds that a consecutive sequence happens X times during N tosses. I'm hoping that the math isn't too difficult from what you have already done.

Thanks,

-Frank

@Frank:

Sorry, I have not - seems like a pretty good problem though!

- Mark

Hi Mark, very interesting piece, but I'm not sure this is right. What are the odds of getting 10 heads in a row in 20 throws? By your method, since Fib 10 is 34, it is 1-(34*(20+2)) / (2^20) =0.999. And how about 20 heads in a row in 20 throws? 1-(4181 * (20 + 2) )/ (2 ^ 20) = 0.912. Unless I've made a mistake somewhere.

@growe:

Yes, you've made a mistake somewhere. You don't want Fib(10), you want the n-step Fib(10). I don't think there is a direct way to calculate this in Mathematica, so I can't lead you to the results easily. However, you can modify the code I included with the article quite easily to get it straight.

- Mark

The zero term of the Poisson Distribution makes a useful

approximation for problems like this. This term means the

probability of no occurences, so subtracting its value from

1 gives the probability of at least one occurence.

find Px = 2 ^ (K +1) where K is run length

find A = N - K -1 where N is the # of tosses

then q = A / Px

and P0 = epsilon ^(-q)

finally, P = 1 - P0

For the (1,000,000)(20) example, the approximation yields

P = 0.379250

Incidently, I've used the inclusive definition of a run,

meaning the run may be of either heads or tails. I did this

to get agreement with Mark's solution. If someone insists

on strictly heads exclusively (or tails exclusively) you

could add 1 to the run length to get the correct answer

for the lower probability.

Art

I have the fibonacci n-step method working for large values

of N. To prevent overflow, I work with chunks of 1,000. The

initial "seed" values are divided by 2 ^ 1000 and thereafter the last 30 of 1000 are divided by that same divisor then

copied to the bottom of a small working array forming a kind of "seed" for the next 1,000. (30 is a max limit I set more or less arbitrarily as a max run length). A final divisor is

of course set as well.

The method is relatively fast. My DOS program does the

(1,000,000)(20) calculation in 7.35 seconds. A recursive

method takes considerably longer (about 2 minutes). This is on a old pentium 4 2 ghz machine.

Art

Not all coins are created equally (and fair). I have a coin that comes up heads 51% of the time; not a big bias. Now what's the probability of at least 20 heads in a row with 1 million flips? Can a small bias make a big difference?

## Leave A Reply

You can insert source code in your comment without fear of too much mangling by tagging it to use the iG:Syntax Hiliter plugin. A typical usage of this plugin will look like this:`[c]`

int main()

{

printf( "Hello, world!\n" );

return 1;

}

[/c]

Note that tags are enclosed in square brackets, not angle brackets. Tags currently supported by this plugin are: as (ActionScript), asp, c, cpp, csharp, css, delphi, html, java, js, mysql, perl, python, ruby, smarty, sql, vb, vbnet, xml, code (Generic).

If you post your comment and you aren't happy with the way it looks, I will do everything I can to edit it to your satisfaction.