# Thread: 100 Coin Flips

1. ## 100 Coin Flips

A fair coin is flipped 100 times. What is the probability (correct to 2 decimal places expressed as a percentage) that you get at least 6 tails in a row?

Tougher question than it looks. I have 2 potential answers:

1. 75.00%
2. 54.61%

What do YOU get!?

2. ## Re: 100 Coin Flips

Originally Posted by Corpsecreate
A fair coin is flipped 100 times. What is the probability (correct to 2 decimal places expressed as a percentage) that you get at least 6 tails in a row?

Tougher question than it looks. I have 2 potential answers:

1. 75.00%
2. 54.61%

What do YOU get!?
I get

3. 66.26%

Sometimes it is easier to find the complementary probability, i.e. the probability that you do not get 6 tails in a row. To that end, there are 2^100 possible sequences of heads or tails, each of which we assume are equally likely. Let $\displaystyle a_n$ be the number of sequences of n heads or tails in which there are not 6 tails in a row. It's easy to see that
$\displaystyle a_n = 2^n$ for $\displaystyle 1 \leq n \leq 5$
and
$\displaystyle a_6 = 2^5$

For $\displaystyle n > 6$, consider the number of acceptable sequences ending in H, T, TT, TTT, TTTT, TTTTT. There are $\displaystyle a_{n-1}, a_{n-2}, a_{n-3}, a_{n-4}, a_{n-5}, \text{ and } a_{n-6}$ of these, respectively. So

$\displaystyle a_n =a_{n-1}+ a_{n-2}+ a_{n-3}+ a_{n-4}+ a_{n-5}+ a_{n-6}$ for $\displaystyle n > 6$

We can use this recurrence to find that
$\displaystyle a_{100} \approx 4.27765 \times 10^{29}$
(I used a spreadsheet)
so the probability that no sequence of 6 tails occurs in 100 flips is approximately

$\displaystyle \frac{4.27765 \times 10^{29}}{2^{100}} = 0.337447$

and the probability that at least one sequence of 6 tails occurs is

$\displaystyle 1- 0.337447 = 0.662553$

3. ## Re: 100 Coin Flips

I ran this problem through a brute force program and the correct answer is 54.61%. An explanation here (not by me):

It's not easy. I thought about it for a while and came up with the correct answer, but I would not characterise it as easy. I'll start by noting you can find the answer here but that doesn't really offer any insight into where it comes from (and I couldn't find an explanation anywhere).

The following is how I worked out the answer, but there may be a simpler way to think of it.

Denote the number of ways to get N tails in a row in A flips by f(A). Obviously, if we flip the coin fewer than N times, there's no chance of getting N tails, so f(A)=0 for A<N. Also obvious is that for A=N, there's exactly one way to do it, so f(N)=1.

Suppose we know the value of f(V) for some V>N. Now what is f(V+1)? Well, we are just adding a flip to the end, which can come up either tails or heads, so each of the ways in f(V) counts twice -- once with a tail at the end and once with a head at the end. But that's not all because there are some positions of V flips where:
(1) there were N-1 tails at the end; and
(2) nowhere in the position were there N tails in a row
Each of those positions of V flips gives rise to one position of V+1 flips where there are N tails in a row because adding one more tail to the end makes it N rather than N-1 tails. Note that condition (2) is important because otherwise we will double count positions that contain N tails in a row.

I will denote the "number of ways of flipping a coin V times such that (1) the last N-1 flips are all tails and (2) nowhere in the V flips are there N tails in a row" by Q(V).

So putting that together, f(V+1) = 2 * f(V) + Q(V)

But what is Q(V)? Well, we know that out of the V flips, the last N flips are fixed: the last N-1 flips have to be tails, and the flip before the tails has to be a head, because otherwise there would be N tails in a row, which would violate condition (2) and mean it's not actually in Q(V). So N flips are fixed which leaves V-N flips free. If those free flips could be totally anything, there would be 2^(V-N) total positions. But in those V-N flips, there can't be N tails in a row. By definition, there are f(V-N) ways of getting N tails in a row in V-N flips, which we have to subtract off.

Therefore, Q(V) = 2^(V-N) - f(V-N).

It turns out that Q(V) is precisely the definition of the V-th Fibonacci N-step number, which is where the formula on that page comes from.

So now we have the following recurrence relation:
f(A) = 0 for A < N,
f(A) = 1 for A = N,
f(A) = 2 * f(A - 1) + Q(A - 1),
Q(V) = 0 for A < N, and
Q(V) = 2^(V-N) - f(V-N) for A >= N.

Using the recurrence relation, you can evaluate f(A) using a computer program or a spreadsheet. And of course, the answer to the original problem is f(100)/2^100 where N=6. The exact answer is 692255904222999797557597756576/2^100.0. This turns out to be approximately 54.61%.

Note that the answer is not 75%. If you mistakenly double count positions where "the last N-1 flips are tails and N tails in a row occurs somewhere", then you will get 75%. In other words, if you incorrectly define Q(V) to be 2^(V-N), then you will get 75%, but it's wrong.

4. ## Re: 100 Coin Flips

Oops, I see I got careless with one of the initial conditions for the recurrence. I should have $\displaystyle a_6 = 63$.

With that change, my answer agrees with Corpsecreate's: $\displaystyle a_{100} \approx 5.75395 \times 10^{29}$, and the probability of at least one run of 6 successive tails is 0.546094.