08-29-2002, 09:44 PM
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
etc.
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.
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
etc.
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.