# Growth and decay of random Fibonacci sequences

Mark Embree, Lloyd N. Trefethen

## Abstract

For 0 < β < β* ≈ 0.70258, solutions to the random recurrencexn+1 =xn±βxn−1 decay exponentially asn→ ∞ with probability one, whereas for β > β*, they grow exponentially. By formulating the problem as a Markov chain involving random matrix products and computing its invariant measure (a fractal) the Lyapunov constant σ(β) = limn→ ∞ |xn|1/n is determined numerically for a wide range of values β, and its dependence on β is observed to be non-smooth. (The limit is defined in the almost sure sense.) This generalizes recent work of Viswanath, who proved σ (1) = 1.131 988 24.... By a simple rescaling, these results also apply to the more general random recurrencexn+1 = αxn± βxn−1 for fixed α and β. These random recurrence relations have links with many fields, including ergodic theory, dynamical systems, heavy–tailed statistics, spectral theory, continued fractions, and condensed matter physics.