Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Thread Tools Display Modes
Old 08-29-2002, 09:44 PM
Posts: n/a
Default Further Thoughts on Fibonacci and Coin Flips

In a thread below, we showed that the probability of getting 2 heads in a row on exactly the Nth toss of a fair coin, and not before the Nth toss, is

F(N)/2^N where F(N) is the Nth Fibonacci number. The Fibonacci numbers are 1,1,2,3,5,8,13,21... where each number is the sum of the preceeding two. See the posts "Your answers their way" under the thread "More Challenging Problems" for a derivation. This result was not mentioned by those who posed this problem, who in fact were off in their numerical answer. I also have not seen this result before, though the probability that I am the first to derive it has got to be close to zero.

It is not too surprising that Fibonacci is involved here since this is essentially a death and renewal process. Fibonacci was interested in the reproductive rates of rabbits. In this case we have sequences of coin flips that terminate (die) and others that continue on to "reproduce". The number of possible sequences that exist in the next generation is proportional to (in this case 2 times) the number that survive to reproduce in the previous generation. The number that die in the next generation before they can reproduce is also proportional (in this case equal) to the number that survive to reproduce in the previous generation.

We can also think of this as a model for natural selection, where 2 heads in a row is a genetic condition that is selected against, since these always die. The remaining sequences of flips will necessarily have the property that they do not have two heads in a row for long stretches.

The sequence that generates the Fibonacci series is

F(n) = [.5+sqrt(5)/2]^n * [.5-sqrt(5)/10] +

[.5-sqrt(5)/2]^n * [.5+sqrt(5)/10]

With all these square roots floating around, you might be amazed that this comes out to integers for every n.

I mentioned that the number .5 + sqrt(5)/2 which appears in this formula is equal to the continued fraction:

1 + 1/(1+1/(1+1/(1+...

and also to sqrt(1+sqrt(1+sqrt(1+...

To see this, in the first case we solve the equation x = 1 + 1/x, and in the second case, we solve x = sqrt(1+x). Both of these give the same quadratic. The roots of the quadratic are .5 +/- sqrt(5)/2. We take the positive result to solve the continued fraction and square root above, but both roots are involved in above equation for F(n).

One other thing to note is that:

1 = 1/1

1 + 1/1 = 2/1

1 + 1/(1+1) = 3/2

1 + 1 /(1+1/(1+1)) = 1+1/(3/2) = 5/3

1 + 1/(1+1/(1+1/(1+1) = 1+1/(5/3) = 8/5

and so on 1 + 1/(1+8/5) = 13/8

1+ 1/(1+13/8) = 21/13


Note that this sequence of numbers also follows a Fibonacci sequence. They are F(n+1)/F(n). The limit of this sequence of numbers is, by definition, the value of the continued fraction

1 + 1/1+1/(1+1/(1+....

And this limit approaches .5 + sqrt(5)/2 = 1.618... for large n. For example, note that 21/13 is already 1.615.

Reply With Quote

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT -4. The time now is 12:50 AM.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.