Random linear recurrence relations

Question

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"

Answer 1

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.

Answer 2

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

Answer 3

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.