No two heads in a row

Suppose I toss a fair coin a 100 times.
What is the probability of not getting two heads in a row?

• This problem has some really big numbers in it. Should be fun. With a possibility of getting between 0 and 50 heads and them not touching another head. Right in the middle the possible outcomes are huge. – Z. Dailey Mar 19 '16 at 16:30
• The answer is a fraction with 'nice' numbers above and below the line. – Alexis Mar 19 '16 at 16:33
• Yah. I know that much. And I think 'nice' might be pushing it. But we've seen fractions with 6+ digit num and denoms on here before. – Z. Dailey Mar 19 '16 at 16:34

The number of possible outcomes for $100$ coin tosses is simply $2^{100}$, which will be our denominator.

For the numerator we must count the number of outcomes without $2$ successive heads. Let us define 2 functions:

• $H(n)$ giving the number of outcomes for $n$ coin tosses without $2$ successive heads which end with heads
• $T(n)$ giving the number of outcomes for $n$ coin tosses without $2$ successive heads which end with tails

For $n=1$ and $n=2$ the results are obviously:

$H(1)=1$
$T(1)=1$

$H(2)=1$
$T(2)=2$

The rest can be calculated recursively. The last toss is allowed to be heads only if the previous toss was tails:

$H(n) = T(n-1)$

And the last toss is allowed to be tails in any case:

$T(n) = H(n-1)+T(n-1) = T(n-2)+T(n-1)$

This is simply the definition of the Fibonacci sequence. For $n=100$ we get:

$H(100)=Fibonacci(100)=354224848179261915075$
$T(100)=Fibonacci(101)=573147844013817084101$

The final numerator is the sum of both this numbers which is of course the next higher number in the Fibonacci sequence ($Fibonacci(102)$).

The final result is:

$$\frac{Fibonacci(102)}{2^{100}} = \frac{927372692193078999176}{1267650600228229401496703205376} \approx 0.00000000073156806144$$

• Actually I can point to a problem in both our answers, because this oeis.org/A008466 was just posted... – Z. Dailey Mar 19 '16 at 17:59
• It should be for fibonacci 102, not 100. The pattern starts at 2,3,5,8... – Z. Dailey Mar 19 '16 at 18:07
• Yes it does confirm your answer... ^vote – Z. Dailey Mar 19 '16 at 18:25

If we tossed 2 times, among all possible outcomes (HT,HH, TT,TH) one of them was getting two head in a row.

$1-\frac{1}{2}\times\frac{1}{2}=\frac{3}{4}$

or not getting 2 heads in a row.

If we tossed 3 times; there could be 8 outcomes and 3 of them were {HHT, HHH} and {THH} so it was;

$\frac{5}{8}$

If we tossed 4 times, there could be 16 outcomes and 8 of them were {HHTT HHHT HHTH HHHH}, {THHT THHH}, {TTHH,HTHH} two head in a row.

$\frac{8}{16}$

In here HTHH comes from not getting HH in a row for the left side of HH. That means we need to multiple with the same possibility for each time!

So if we generalize this; there are 99 position that you can put HH in the outcomes for 100 tosses from the beginning to the end such as HHTHTTTHTH....TTH (HH is position in the beginning). and you should not count the same possibilities again so it becomes half every time you move to the right for n tosses;

if n = 10; This is how we are supposed to calculate the probability! $2^x$ comes from the above where no H in the right hand side of the HH sequence.

$\ Reverse \ or R(x)$ comes from where H exist on the left hand side of HH but there is no HH in a row and every time you encounter with this possibility, you need to multiply it with $2^x$.

Moreover, the reverse function is actually easy to calculate;

$R(x)=R(x+1)+R(x+2)$ where $R(n-2)=1$ & $R(n-3)=1$.

As a result we get; • $\frac{9}{16}$ ? In binary $(H=1)$ you get a 11 for the numbers: 3, 6, 7, 11, 12, 13, 14, 15 . So I count $\frac{8}{16}$. – Varon Mar 19 '16 at 17:01
• Yeah, you missed HTHH up there. You might need to reevaluate your function. :-) – InternetHobo Mar 19 '16 at 17:13
• @Varon I wrote all possibilities, which outcome do I miss? tell me with possible outcome instead of $\frac{8}{16}$ in terms of H and T please. – Oray Mar 19 '16 at 17:14
• @InternetHobo damn you are right :( – Oray Mar 19 '16 at 17:14

Solution

$\frac{115921586524134874897}{158456325028528675187087900672}$

General Formula

$\frac{F_{n+2}}{2^n}$ for $F(n) = n^{th}$ Fibonacci number

Reason

It's the opposite of OEIS A008466

Toss a fair coin n times; a(n) is number of possible outcomes having a run of 2 or more heads. $a(n) = 2^n - Fibonacci(n+2)$

List up to 20 coins

2 coins : 3 / 4
3 coins : 5 / 8
4 coins : 8 / 16
5 coins : 13 / 32
6 coins : 21 / 64
7 coins : 34 / 128
8 coins : 55 / 256
9 coins : 89 / 512
10 coins : 144 / 1024
11 coins : 233 / 2048
12 coins : 377 / 4096
13 coins : 610 / 8192
14 coins : 987 / 16384
15 coins : 1597 / 32768
16 coins : 2584 / 65536
17 coins : 4181 / 131072
18 coins : 6765 / 262144
19 coins : 10946 / 524288
20 coins : 17711 / 1048576

Source: https://oeis.org/A008466

• The opposite of $2^n - Fibonacci(n+2)$ is $2^n - (2^n - Fibonacci(n+2)) = Fibonacci(n+2)$ which is what I got in my answer. – Sleafar Mar 19 '16 at 18:03