# Solving randomized recurrence relation

I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and $$x_{n+1}=2x_n\pm x_{n-1}$$ 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.

-
Thank you very much! – alext87 Sep 13 '10 at 19:42

To start with: the sequence can be written as $$x_{n+1} = 2 x_{n} + e_{n+1} x_{n-1} \; [1]$$

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:

$$E(x^2_{n+1})=2E(x_n x_{n+1}) + E(e_{n+1} x_{n+1} x_{n-1}) \; [2]$$

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

$$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]$$

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

$$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]$$

Hence

$$E(x_{n+1}^2) = 4 E(x^2_n) + E(x^2_{n-1}) \; [5]$$

====

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. – alext87 Sep 13 '10 at 17:19
No, but if it converges, it should work. Id didnt prove it converges. – leonbloy Sep 13 '10 at 17:25
I just ran a simulation of my own, the answer definitely isn't 2. – Oscar Cunningham Sep 13 '10 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. – whuber Sep 13 '10 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. – alext87 Sep 13 '10 at 18:13

I've been testing a new math search engine and found a similar discussion on the mathoverflow, there is link to search results (http://uniquation.com/en/solutions.aspx?query=F_{n%2B1}%3D2F_n%2BF_{n-1})

-