Random Fibonacci sequence: Difference between revisions

Revision as of 16:45, 17 June 2007

Revision as of 21:30, 6 July 2007

Line 16:

The constant was computed by [[Divakar Viswanath]] in 1999 (see references). His work uses the theory of random matrix product developed by [[Hillel Furstenberg|Furstenberg]] and [[Harry Kesten|Kesten]], the [[Stern-Brocot tree]], and a computer calculation using [[floating point]] arithmetics validated by an analysis of the [[rounding error]].

[[Johannes Kepler]] had shown that for normal Fibonacci sequences (where the randomness of the sign does not occur), the ratio of the successive numbers converged to the [[golden mean]], which is approximately 1.618. Thus, for any large ''n'', the golden mean constantmay raisedbe toapproximate thewith powerastonishing ofaccuracy ''n''by yieldsdividing by the nthprevious termnumber ofin the sequence, with astonishing accuracy.

The random Fibonacci sequence, defined above, is the same as the normal Fibonacci sequence if always the plus sign is chosen. On the other hand, if the signs are chosen as minus-plus-plus-minus-plus-plus-..., then we get the sequence 1,1,0,1,1,0,1,1,... However, such patterns occur with probability zero in a random experiment. Surprisingly, the ''n''th root of |''f''_''n''| converges to fixed value with probability one.