# Random Fibonacci sequence

(Redirected from 1.13198824)

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

${\displaystyle 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},

${\displaystyle 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

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle {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

${\displaystyle {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:

${\displaystyle 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 ${\displaystyle \varphi =(1+{\sqrt {5}})/2,}$ which is approximately 1.61803. In 1765, Leonhard Euler published an explicit formula, known today as the Binet formula,

${\displaystyle 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:

${\displaystyle {\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

${\displaystyle 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.
2. ^ Oliveira, J. O. B.; De Figueiredo, L. H. (2002). "Interval Computation of Viswanath's Constant". Reliable Computing. 8 (2): 131. doi:10.1023/A:1014702122205.
3. ^ Makover, E.; McGowan, J. (2006). "An elementary proof that random Fibonacci sequences grow exponentially". Journal of Number Theory. 121: 40. arXiv:. doi:10.1016/j.jnt.2006.01.002.
4. ^ Embree, M.; Trefethen, L. N. (1999). "Growth and decay of random Fibonacci sequences" (PDF). Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. doi:10.1098/rspa.1999.0412.