**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"



Random linear recurrence relations
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.


