Royal Society Publishing

Growth and decay of random Fibonacci sequences

Mark Embree, Lloyd N. Trefethen


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.

Royal Society Login

Log in through your institution