Solving randomized recurrence relation

Question

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.

Thanks in advance.

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.

Answer 1

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.

Answer 2

To start with: the sequence can be written as \begin{equation} x_{n+1} = 2 x_{n} + e_{n+1} x_{n-1} \; [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}) \; [2] \end{equation}

To compute the first term we multiply [1] 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) \; [3] \end{equation}

To compute the second term we multiply [1] 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) \; [4] \end{equation}

Hence

\begin{equation} E(x_{n+1}^2) = 4 E(x^2_n) + E(x^2_{n-1}) \; [5] \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.