# Random Fibonacci sequence

In mathematics, the random Fibonacci sequence is a stochastic analogue of the Fibonacci sequence defined by the recurrence relation fn = fn−1 ± fn−2, where the signs + or − are chosen at random with equal probability 1/2, independently for different n. By a theorem of Harry Kesten and Hillel Furstenberg, random recurrent sequences of this kind grow at a certain exponential rate, but it is difficult to compute the rate explicitly. In 1999, Divakar Viswanath showed that the growth rate of the random Fibonacci sequence is equal to 1.1319882487943…, a mathematical constant that was later named Viswanath's constant.[1][2][3]

## Description

The random Fibonacci sequence is an integer random sequence {fn}, where f1 = f2 = 1 and the subsequent terms are determined from the random recurrence relation

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

A run of the random Fibonacci sequence starts with 1,1 and the value of the each subsequent term is determined by a fair coin toss: given two consecutive elements of the sequence, the next element is either their sum or their difference with probability 1/2, independently of all the choices made previously. If in the random Fibonacci sequence the plus sign is chosen at each step, the corresponding run is the Fibonacci sequence {Fn},

$1,1,2,3,5,8,13,21,34,55,\ldots.$

If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence

$1,1,0,1,1,0,1,1,0,1,\ldots.$

However, such patterns occur with vanishing probability in a random experiment. In a typical run, the terms will not follow a predictable pattern:

$1, 1, 2, 3, 1, -2, -3, -5, -2, -3, \ldots \text{ for the signs } +, +, +, -, -, +, -, -, \ldots.$

Similarly to the deterministic case, the random Fibonacci sequence may be profitably described via matrices:

${f_{n-1} \choose f_{n}} = \begin{pmatrix} 0 & 1 \\ \pm 1 & 1 \end{pmatrix} {f_{n-2} \choose f_{n-1}},$

where the signs are chosen independently for different n with equal probabilities for + or −. Thus

${f_{n-1} \choose f_{n}} = M_{n}M_{n-1}\ldots M_3{f_{1} \choose f_{2}},$

where {Mk} is a sequence of independent identically distributed random matrices taking values A or B with probability 1/2:

$A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 0 & 1 \\ -1 & 1 \end{pmatrix}.$

## Growth rate

Johannes Kepler discovered that as n increases, the ratio of the successive terms of the Fibonacci sequence {Fn} approaches the golden ratio $\varphi=(1+\sqrt{5})/2,$ which is approximately 1.61803. In 1765, Leonhard Euler published an explicit formula, known today as the Binet formula,

$F_n = {{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}.$

It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio φ.

In 1960, Hillel Furstenberg and Harry Kesten showed that for a general class of random matrix products, the norm grows as λn, where n is the number of factors. Their results apply to a broad class of random sequence generating processes that includes the random Fibonacci sequence. As a consequence, the nth root of |fn| converges to a constant value almost surely, or with probability one:

$\sqrt[n]{|f_n|} \to 1.13198824\dots \text{ as } n \to \infty.$

An explicit expression for this constant was found by Divakar Viswanath in 1999. It uses Furstenberg's formula for the Lyapunov exponent of a random matrix product and integration over a certain fractal measure on the Stern–Brocot tree. Moreover, Viswanath computed the numerical value above using floating point arithmetics validated by an analysis of the rounding error.

## Related work

The Embree–Trefethen constant describes the qualitative behavior of the random sequence with the recurrence relation

$f_n=f_{n-1}\pm \beta f_{n-2}$

for different values of β.[4]

## References

1. ^ Viswanath, D. (1999). "Random Fibonacci sequences and the number $1.13198824\dots$". Mathematics of Computation 69 (231): 1131–1155. doi:10.1090/S0025-5718-99-01145-X. edit
2. ^ Oliveira, J. O. B.; De Figueiredo, L. H. (2002). Reliable Computing 8 (2): 131. doi:10.1023/A:1014702122205. edit
3. ^ Makover, E.; McGowan, J. (2006). "An elementary proof that random Fibonacci sequences grow exponentially". Journal of Number Theory 121: 40. doi:10.1016/j.jnt.2006.01.002. edit arXiv:math.NT/0510159
4. ^ Embree, M.; Trefethen, L. N. (1999). "Growth and decay of random Fibonacci sequences". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. doi:10.1098/rspa.1999.0412.