Random Fibonacci sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]


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}.

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},


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


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[edit]

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[edit]

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]


  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. doi:10.1016/j.jnt.2006.01.002.  arXiv:math.NT/0510159
  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. 

External links[edit]