lotus

previous page: 403 probability/flips/once.in.run.p
  
page up: Puzzles FAQ
  
next page: 405 probability/flips/unfair.p

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:













TOP
previous page: 403 probability/flips/once.in.run.p
  
page up: Puzzles FAQ
  
next page: 405 probability/flips/unfair.p