# 404 probability/flips/twice.in.run.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 404 probability/flips/twice.in.run.p

What is the probability in n flips of a fair coin that there will be two

heads in a row?

probability/flips/twice.in.run.s

Well, the question is then how many strings of n h's and t's contain

hh? I would guess right off hand that its going to be easier to

calculate the number of strings that _don't_ contain hh and then

subtract that from the total number of strings.

So we want to count the strings of n h's and t's with no hh in them.

How many h's and t's can there be? It is fairly clear that there must

be from 0 to n/2 h's, inclusive. (If there were (n/2+1) then there

would have to be two touching.)

How many strings are there with 0 h's? 1

How many strings are there with 1 h? Well, there are (n-1) t's, so

there are a total of n places to put the one h. So the are nC1 such

strings. How many strings are there with 2 h's? Well, there are (n-1)

places to put the two h's, so there are (n-1)C2 such strings.

Finally, with n/2 h's there are (n/2+1) places to put them, so there

are (n/2+1)C(n/2) such strings.

Therefore the total number of strings is

Sum (from i=0 to n/2) of (n-i+1)C(i)

Now, here's where it get's interesting. If we play around with Pascal's

triangle for a while, we see that this sum equals none other than the

(n+2)th Fibonacci number.

So the probability that n coin tosses will give a hh is:

2^n-f(n+2)

----------

2^n

(where f(x) is the xth Fibanocci number (so that f(1) is and f(2) are both 1))

Continue to: