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.

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} \; [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}


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

  • $\begingroup$ I don't think this logic works $\mathbb{E}(X^{1/n})\neq\mathbb{E}(X)^{1/n}$ in general. $\endgroup$ – alext87 Sep 13 '10 at 17:19
  • $\begingroup$ No, but if it converges, it should work. Id didnt prove it converges. $\endgroup$ – leonbloy Sep 13 '10 at 17:25
  • 1
    $\begingroup$ I just ran a simulation of my own, the answer definitely isn't 2. $\endgroup$ – Oscar Cunningham Sep 13 '10 at 17:47
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Sep 13 '10 at 17:54
  • 1
    $\begingroup$ @whuber: your idea looks promising, if you have time can you explain how we can get $m$ and $s$. Thanks in advance. $\endgroup$ – 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})


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.