# Random linear recurrence relations

Problem

I am interested in the random recurrence relation of the form $x_{n+1}=\alpha x_n \pm \beta x_{n-1}$ where $\alpha$, $\beta$ are known constants and the $\pm$ sign is chosen with equal probability.

In particular I would like to investigate the limit of $|x_n|^{1/n}$ as $n\rightarrow\infty$. (i.e the exponential growth rate)

Motivation

I was considering the problem of finding $\lim_{n\rightarrow\infty}|x_n|^{\frac{1}{n}}$ where $x_n$ is the solution to $x_{n+1}=2x_n \pm x_{n-1}$, $x_0=x_1=1$. All numerical evidence suggests that $\lim_{n\rightarrow\infty}|x_n|^{\frac{1}{n}}\approx 1.91$ almost surely but I am having difficulty even proving that the sequence almost surely convergences.

Survey

The solution to the recurrence relation of the from $x_{n+1}=x_n \pm \beta x_{n-1}$ has been show to have expontential growth almost surely. See http://en.wikipedia.org/wiki/Embree%E2%80%93Trefethen_constant

Also there has been work on the random fibonacci sequence $x_{n+1}=x_n \pm x_{n-1}$ for example Viswanath(2000), "Random Fibonacci sequences and the number 1.13198824"

-
Does any of the answers below correspond to what you were asking for? –  Did Apr 11 '11 at 17:10

If $(x_n)$ solves the recursion you are interested in, then the sequence $(y_n)$ of general term $y_n=x_n/\alpha^n$ is a random Fibonacci sequence such as in the Embree-Trefethen page you linked to.

-
That was so obvious! I am assuming getting an analytical expression for the growth rate is out of the question. –  alext87 Sep 16 '10 at 15:38
Indeed. Viswanath's paper is a very readable account to this stuff--and includes the value of the growth rate when your parameters are such that $\beta=\alpha^2$... –  Did Sep 16 '10 at 18:10

You question amounts to proving that the norms of products of i.i.d. random matrices $({{\alpha \;\;\pm\beta}\atop{1\;\;\;\; 0}})$ have a non-zero exponential growth rate. This is a particular case of a famous theorem of Furstenberg ("Non-commuting random products", 1963) on positivity of the top Lyapunov exponent for products of random matrices. Existence of the limit a.e. is an earlier theorem of Furstenberg and Kesten, which is nowadays proved by referring to Kingman's subadditive ergodic theorem.

-

Please see the paper "Random Fibonacci Sequences" by Clement Sire: http://arxiv.org/PS_cache/cond-mat/pdf/0106/0106457v1.pdf where you find weak and strong disorder expansions and also analytical results. (I worked together with Clement Sire about 15 years ago.)

-