Random Fibonacci sequence

A random Fibonacci sequence is a variant of the Fibonacci sequence, defined by the recurrence relation f_n = ±f_n−1 ± f_n−2 with the signs chosen randomly. Viswanath's constant is a mathematical constant measuring how fast random Fibonacci sequences grow. The value of Viswanath's constant is approximately 1.13198824.

Definitions

A random Fibonacci sequence is a sequence of numbers f_n with the following recursive definition: f₁ = 1, f₂ = 1, and

$f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\mbox{with probability 0.25}};\\f_{n-1}-f_{n-2},&{\mbox{with probability 0.25}};\\-f_{n-1}+f_{n-2},&{\mbox{with probability 0.25}};\\-f_{n-1}-f_{n-2},&{\mbox{with probability 0.25}}.\end{cases}}$

In other words, given the previous two elements of the sequence, there are four possible formulas for the next element, corresponding to the four choices for the two signs. The decision which formula to use is taken at random with a probability of 0.25 favouring each possibility.

The name is derived from relation to Fibonacci numbers: If the two terms in the right hand side of the equation above are taken with positive sign,

$f_{n}=f_{n-1}+f_{n-2}\,$

then the sequence {f_n} is of Fibonacci numbers.

Viswanath's constant is defined as the exponential rate at which the average absolute value of a random Fibonacci sequence increases. In a random Fibonacci sequence {f_n}, with a probability of 1 (i.e. with extremely rare exceptions, almost surely) the nth root of the absolute value of the nth term in the sequence converges to the value of the constant, for large values of n. In symbols,

${\sqrt[{n}]{|f_{n}|}}\to 1.13198824\dots {\mbox{ as }}n\to \infty .$

Explanation

The constant was computed by Divakar Viswanath in 1999 (see references). His work uses the theory of random matrix product developed by Furstenberg and 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 (or ratio), which is approximately 1.61803. Thus, for any large n, the golden mean may be approximated with astonishing accuracy by dividing by the previous number in the sequence. In 1765, Leonhard Euler published a formula establishing that

$f_{n}={\frac {1}{\sqrt {5}}}(\phi ^{n}-(-1)^{n}\phi ^{-n})$,

with

$\phi =(1+{\sqrt {5}})/2=1.61803\ldots$

the golden mean. Of course, $f_{n+1}/f_{n}\to \phi$ as $n\to \infty$. This formula was rediscovered by Jacques Binet in 1843.

The random Fibonacci sequence, defined above, is the same as the normal Fibonacci sequence if the plus sign is always 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 almost zero in a random experiment. Surprisingly, the nth root of |f_n| converges to fixed value with probability almost one.

Significance

In 1960, Hillel Furstenberg and Harry Kesten had shown that for a general class of random matrix products, the absolute value of the norm of product of n factors converges to a power of a fixed constant. This is a broad class of random sequence-generating processes, which includes the random Fibonacci sequence. This proof was significant in advances in laser technology and the study of glasses. The Nobel Prize for Physics in 1977 went to Philip Warren Anderson of Bell Laboratories, Sir Nevill Francis Mott of Cambridge University in England, and John Hasbrouck van Vleck of Harvard "for their fundamental theoretical investigations of the electronic structure of magnetic and disordered systems".

Viswanath's proof, by specifying the value of the constant number in this case, has helped make this area more accessible for direct study. Viswanath's constant may explain the case of rabbits randomly allowed to prey on each other. (See Fibonacci sequence for the original statement of the rabbit problem.) This step would allow closer simulation of real world scenarios in various applications.

See also

The Embree-Trefethen constant describes the behaviour of the random sequence f_n = f_n−1 ± βf_n−2 for different values of β.

References

• Viswanath, Divakar (1999), "Random Fibonacci sequences and the number 1.13198824…", Mathematics of Computation, 69 (231): 1131–1155, doi:10.1090/S0025-5718-99-01145-X.

• Oliveira, J.B.; de Figueiredo, L.H. (2002), "Interval computation of Viswanath's constant", Reliable Computing, 8 (2): 131–138., doi:10.1023/A:1014702122205

• Makover, Eran; McGowan, Jeffrey (2006), "An elementary proof that random Fibonacci sequences grow exponentially", Journal of Number Theory, 121 (1): 40–44, doi:10.1016/j.jnt.2006.01.002 arXiv:math.NT .

External links

• A brief explanation
• Weisstein, Eric W. "Random Fibonacci Sequence". MathWorld.
• Sloane, N. J. A. (ed.). "Sequence A078416". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.