# Coin Toss Streak Calculator

*The Longest Run of Heads;*The College Mathematics Journal 21 (3), 196β207; 1990

Whatever math problem related to the **probability of obtaining a streak in coin tosses** brought you here, you're at the right place β Omni's **coin toss streak calculator** will help you learn all the interesting things stemming from this simple observation that sometimes **consecutive heads** appear when we toss a coin (to our Witcher of course). In the article below we:

- Tell you what coin flip streaks are;
- Go through
**examples**of computing the probability of runs in coin tosses; and - Explain
**how to derive a formula**for the probability of runs in coin flips.

## What are streaks in coin flips?

When you toss a coin it can come up heads or tails. We talk about * streaks* (or

*) when we're interested in getting*

**runs****the same result several times in a row**. Most often, we're interested in the longest streak in a given number of tosses.

In contrast to the standard coin toss problem (which you can discover with our coin flip probability calculator), where we only care about how many heads appeared in a given number of flips, in the streak problem the order of getting the results matters: in `HHHTH`

there's a streak of `3`

heads in `5`

coin flips, which is different from `HHTHH`

containing a run of `2`

heads, even though in both cases we have `4`

heads in total.

Computing the probability of runs in coin flips in not a trivial problem. Before we dive into the theory and discuss how to derive a formula for the probability of runs in coin toss, let's quickly explain how our coin toss streak calculator works, so that you can use it as we go through the calculations.

π To get familiar with the math theory of probability, try our probability calculator.

## How to use this coin toss streak calculator?

To determine the probability of runs in coin flips with our coin toss streak calculator, follow these steps:

- Tell us
**how many coin tosses**there are in total. - Enter the
**length of streaks**you're interested in. - Finally, tell us if you're interested in:
- streaks of
**exactly**this length; - streaks of
**at least**this length; or - streaks of
**at most**this length.

- streaks of
- The results will appear underneath. If there's 30 flips of less, you can choose between the exact probability (in the form of a fraction) and its approximation.
- Also, if you wish, we will display the plot of the probability distribution of the streak you're interested in. This feature is available for up to 100 tosses.

Play for a little while with the coin toss streak calculator to get the gist of the math challenge at hand before we get our hands dirty with some computations.

## Examples of runs probability in coin flips

We'll start softly by going through an example of three coin flips. Obviously, there's eight possible results:

`HHH, HHT, HTH, THH, HTT, THT, TTH, TTT`

The lengths of the longest streak of heads are, respectively:

`3, 2, 1, 2, 1, 1, 1, 0 `

and so we get the following distribution:

exact streak length | probability |
---|---|

0 | 1/8 |

1 | 4/8 |

2 | 2/8 |

3 | 1/8 |

That is, in words, there's `25%`

chance that we'll get the streak of **exactly** two heads while tossing a coin three times. You can verify these results with the help of our coin toss streak calculator.

π Observe that the above *exact* distribution is **not** symmetric!

Now it's easy to find the probability of getting streaks of **at least** or **at most** some length. It's logical that we're interested in them, because the streak of three heads contains a streak of two heads, right?

Let's repeat what we've done above and note that there is:

- one result (
`HHH`

) that has**at least three**heads in a row - three results (
`HHH, HHT, THH`

) that have**at least two**heads in a row - seven results (all except
`TTT`

) that have**at least one**head in a row (the concept of*heads in a row*becomes more abstract now but bear with us) - eight results (so all of them) that have
**at least zero**heads in a row (so any result will do).

This can be summarized as follows:

min streak length | probability |
---|---|

0 | 1 |

1 | 7/8 |

2 | 3/8 |

3 | 1/8 |

As for the streaks of **at most** some length, we very similarly deduce that there is:

- one result (
`TTT`

) that has**at most zero**heads in a row. - five results (
`TTT, HTH, HHT, THH`

) that have**at most one**heads in a row. - seven results (all except
`HHH`

) that have**at most two**heads in a row. - eight results (all) that have
**at most three**heads in a row (because there's three coin tosses in total).

max streak length | probability |
---|---|

0 | 1/8 |

1 | 5/8 |

2 | 7/8 |

3 | 1 |

π Observe that the *min length* and *max length* tables are **not** mirror images one of the other!

It turns out the easiest value to derive here is the probability of a max streak length. Then, from it, we can easily obtain the remaining two. Let's go!

## How to find the probability of streaks in coin toss?

From this point forward, we'll use $L$ to denote the length of the longest streak of heads in a string of $n$ fair coin flip outcomes. Recall that each possible coin toss sequence resulting from $n$ coin tosses has the same probability $1/2^n$. Hence, the probability $P(L \leq k)$ that the longest run of heads will consist of $k$ or fewer heads is $P(L \leq k) = f(k,n)/2^n$. Here, $f(k,n)$ denotes the number of results that contain streaks of heads whose length does not exceed $k$.

Our task is, therefore, to find a way to compute $f(k,n)$. It's obvious that if $k \geq n$ then $f(k,n) = 2^n$, because we cannot get a streak longer than the total number of cases. Therefore, we assume $k < n$.

Imagine you start tossing the coin. At some point, you start getting consecutive heads. As they appear, you get more and more nervous β because you don't want to observe more than $k$ heads in a row (I feel you can feel that pressure growing). But, suddenly, *phew*, what a relief β there's tails! The game is in fact re-set: we will start counting the streak of heads from zero again.

In fact, this simple observation is the main principle on which the reasoning here is based! More precisely, what matters is how long you wait till your first `T`

:

- If you got
`T`

in the very first toss, then there's $f(k,n-1)$ sequences having at most $k$ consecutive heads in the remaining $n-1$ tosses. - If you started with
`HT`

, then there's $f(k,n-2)$ sequences having at most $k$ consecutive heads in the remaining $n-2$ tosses. - If you started with
`HHT`

, then there's $f(k,n-3)$ sequences having at most $k$ consecutive heads in the remaining $n-3$ tosses. - And so on. We bet you can see the rule.
- The longest you can wait for your first
`T`

is until the $k+1$-th toss. (Otherwise you'd get more than $k$ consecutive heads and it's a game over). Then there's $f(k,n-k-1)$ sequences having at most $k$ consecutive heads in the remaining $n-k-1$ tosses.

Since we consider strings of results that have different beginnings (`T, HT, HHT`

, etc.), we're sure not to count anything twice. So we can safely sum what we got above to get the total number of strings that have no streaks of more than `k`

heads:

Clearly, to actually compute the values of $f(k,n)$ using the recurrence relations given above, we need the initial conditions. That is, the values of $f(k,n)$ for small values of $n$. In fact, we need $k+1$ of them: $f(k,0), f(k,1), \ldots, f(k,k)$. And then we will be able to compute $f(k,k+1)$ as the sum of these initial values.

So what are these initial values? Note there's fewer coin tosses than the length of head streak we consider. Oh, we've already discussed this case and it was just the powers of two: $f(k,j) = 2^j$. In particular, $f(k,0) = 1$ because if we don't toss, the only possible result is the empty string, and it definitely contains no consecutive heads (it does not contain anything, in fact).

Okay, so we now know how to determine the probability that the longest streak of heads does not exceed some given length. This is what we've referred to as the *at-most* case. How to derive the *exact* and *at-least* thing?

The * at-least* case calls for the complement of the

*at-most*case. That is, the probability that the longest streak of heads is of length at least $k$ reads:

Finally, the probability that the longest streak in $n$ tosses is * exactly* of length $k$ is simply the difference between it being of length at most $k$ and at most $k-1$:

π If you're familiar with the language of probability theory, you can easily recognize that we've just calculated the **probability mass function** from the **cumulative distribution function**.

## Consecutive heads & k-step Fibonacci sequences

Let's discuss in more details the case of $k = 1$. Rewriting the formula for $f(k,n)$ from the previous section, we obtain:

The initial condition are $f(k,0) = 1$ and $f(k,1) = 2$. Then we get $f(k,2) = 3$, $f(k,3) = 5$, $f(k,4) = 8$. Yes, you've recognized it correctly! What we've got here is the world-famous Fibonacci sequence (even though the indices are slightly shifted)! Wow, we knew that Fibonacci numbers appear **everywhere**, but have you expected them here? π€―

π Go to our Fibonacci sequence calculator if you're not yet familiar with this celebrated math concept.

For larger values of $k$ we obtain the so-called * m-step Fibonacci sequence* with $m = k+1$. The idea is that the next term is the sum of the $m$ previous terms. So, for $k=1$ we've had 2-step Fibonacci sequence (just the standard Fibonacci), for $k=2$ we'll get 3-step Fibonacci sequence, etc. Here's a quick summary of them:

m | Name | Several initial terms |
---|---|---|

2 | Fibonacci | 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 |

3 | Tribonacci | 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927 |

4 | Tetranacci | 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490 |

5 | Pentanacci | 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793 |

6 | Hexanacci | 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936 |

7 | Heptanacci | 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000 |

8 | Octonacci | 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028 |

9 | Nonanacci | 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040 |

10 | Decanacci | 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045 |

π The prefixes above (tri-, tetra-, penta-, etc) correspond to numbers in the great Greek language. You've certainly seen them already in words like *tri*angle, *tetra*hedron, *penta*gon, etc. They just tell us how many previous terms we need to add up to get the next term: for *Tetra*nacci it's four, for *Octo*nacci it's eight, etc.

## Finding the coin toss streak probability β an example

Let's find the probability of getting a streak of at least 3 heads with 10 flips. According to what we've established above, we have

and $f(2,10)$ is the tenth term of the Tribonacci sequence ($m = k+1$). Looking into the table above, we see $f(2,10) = 504$ (remember, the term numbering starts from zero). As a result, we get:

So you have around a fifty percent chance of getting a streak of at least three heads if you flip a coin ten times. Pretty high chance, isn't it? For at least four consecutive heads the probability falls to around 25%, for streaks of five heads or more it's still around 10%, and then for six it's a bit less than 5%.

## FAQ

### What is a recurrence relation?

A **recurrence relation** means that the `n`

-th term of a sequence is expressed as some combination (e.g., a sum) of the previous terms of this sequence. A sufficient number of initial values must be defined for this procedure to work!

### How do I find the probability of streaks in coin toss?

To find the probability of the length of the longest head run not exceeding `k`

:

- Compute
`2`

to the power of`n`

, where`n`

is the total number of coin flips you perform. - Determine the
`n`

-th term of the`(k+1)`

-step Fibonacci sequence. - Divide the number obtained in Step 2 by that from Step 1.
- What you got is exactly the probability we've been looking for!

### What is the probability of no consecutive heads in 3 coin flips?

The probability that in 3 coin tosses you'll get no consecutive heads is `62.5%`

. The possible sequences you can obtain with 3 coin tosses are `HHH, HHT, HTH, THH, HTT, THT, TTH, TTT`

. Of these 8 possible sequences, 5 have no consecutive heads: `HTH, HTT, THT, TTH, TTT`

. Therefore, the probability is `5/8`

, which is `62.5%`

.

### What is the probability of no consecutive heads in 10 coin flips?

The probability that no consecutive heads come up in 10 coin flips is around `14%`

.