# Solving randomized recurrence relation

I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and \begin{equation} x_{n+1}=2x_n\pm x_{n-1} \end{equation} where we choose the $\pm$ sign independently with equal probability. Now considering the recurrence relations $x_{n+1}=2x_n+x_{n-1}$ and $x_{n+1}=2x_n-x_{n-1}$ separately, it is clear that $x_n\rightarrow\infty$ as $n\rightarrow\infty$. However, the sequence $x_n^{1/n}$ seems to tend to a limit near 1.91 (got this from numerical computation and some brute force by a Monte Carlo simulating the $\pm$ sign). Thus the sequence $x_n^{1/n}$ seems to convenge almost surely. I was wondering if anyone could show that the sequence was indeed almost surely converging and/or work out the limit.

Update:
This comment shows that $\lim_{n\rightarrow\infty} |x_n|^{1/n}$ converges almost surely. Let $y_n=\frac{x_n}{2^n}$ then $2^{n+1}y_{n+1}=2^{n+1}y_n\pm 2^{n-1}y_{n-1}$. Hence

$y_{n+1}=y_n\pm \frac{1}{4}y_{n-1}$

Embree-Trefethen showed that $\lim_{n\rightarrow\infty} |y_n|^{1/n}$ converges almost surely. See Embree, M.; Trefethen, L. N. (1999), "Growth and decay of random Fibonacci sequences".

However, finding the almost sure limit accurately or analytically is proving difficult at the moment.

If you replace 2 with 1 in your recurrence, you get the random Fibonacci sequence. Viswanath has proven that the random Fibonacci sequence almost surely has exponential growth (and gives the growth constant). I haven't carefully read the proof, though, so I can't comment on how it could be adapted to the case you're interested in.

Kesten and Furstenberg showed quite a while ago that the limit you say is around 1.91 at least exists, by restating the problem as one about multiplication of random matrices.

To start with: the sequence can be written as \begin{equation} x_{n+1} = 2 x_{n} + e_{n+1} x_{n-1} \;  \end{equation}

where $e_n$ is a sequence of iid Bernoully variables taking the values $(1,-1)$ with equal probabilities.

Now, taking expectations, and because $e_{n+1}$ and $x_{n-1}$ are independent, it results that $E(x_n) = 2^{n-1}$

Hence, I'd say that, if the sequence $x_n^{1/n}$ converges, it should converge to 2.

== continued ==

Let's see if we can compute the variance. Multiplying by $x_{n+1}$ and taking expectations:

\begin{equation} E(x^2_{n+1})=2E(x_n x_{n+1}) + E(e_{n+1} x_{n+1} x_{n-1}) \;  \end{equation}

To compute the first term we multiply  by $x_{n}$

\begin{equation} E(x_n x_{n+1})= 2 E(x_n^2) + E(e_{n+1} x_{n} x_{n-1}) = 2 E(x_n^2) \;  \end{equation}

To compute the second term we multiply  by $e_{n+1} x_{m-1}$ and recall that $e_{n+1}^2 =1$

\begin{equation} E(e_{n+1} x_{n+1} x_{n-1}) = 2 E(e_{n+1} x_{n-1} x_{n}) + E(e_{n+1}^2) = E(e_{n+1}^2) \;  \end{equation}

Hence

\begin{equation} E(x_{n+1}^2) = 4 E(x^2_n) + E(x^2_{n-1}) \;  \end{equation}

====

Updated: this doesnt lead where I expected to ... I thought that the linearly-normalized sequence (say, $x_n / 2^n$ ) would have an asymtotically vanishing variance, but this does not appear to be so.

• I don't think this logic works $\mathbb{E}(X^{1/n})\neq\mathbb{E}(X)^{1/n}$ in general. Sep 13, 2010 at 17:19
• No, but if it converges, it should work. Id didnt prove it converges. Sep 13, 2010 at 17:25
• I just ran a simulation of my own, the answer definitely isn't 2. Sep 13, 2010 at 17:47
• The answer isn't 2 because the limiting distribution is lognormal, which is asymmetric. But you can use a similar recursion to find the asymptotic variance and then apply the well-known formulae connecting mean and variance of normal and lognormal variables to obtain the answer. (I.e., lognormal mean is exp(m) and lognormal variance is exp(m + s^2/2) where m and s^2 are the normal mean and variance, resp.) These formulae show right away that the limiting value must be strictly less than 2. Sep 13, 2010 at 17:54
• @whuber: your idea looks promising, if you have time can you explain how we can get $m$ and $s$. Thanks in advance. Sep 13, 2010 at 18:13