I have recently been toying (very superficially) with the random Fibonacci sequence, i.e., defined by $F_0=1=F_1=1$ and $$ F_{n} = F_{n-1} + \varepsilon_n F_{n-2} $$ where $(\varepsilon_n)_{n\geq 2}$ is a sequence of i.i.d. Rademacher random variables.

It is known that this sequence is such that $$ |F_n|^{1/n} \xrightarrow[n\to\infty]{\rm a.s.} \nu $$ where $\nu \approx 1.13$ is the Viswanath constant (D. Viswanath, 1999).

I am interested in the case where the $(\varepsilon_n)_{n\geq 2}$ are no longer uniform in $\{-1,1\}$, but instead $1$ with probability $p\in[0,1]$ (so the standard Fibonacci sequence corresponds to $p=1$, and the standard random Fibonacci sequence to $p=1/2$). Then my understanding is that the convergence proof goes through, i.e., $$ |F_n|^{1/n} \xrightarrow[n\to\infty]{\rm a.s.} \nu(p) $$ I am interested in the behavior of $\nu(p)$ as a function of $p$. Is there anything known about it?

Through some basic simulations, the behavior seems very regular, but I am not sure what else to infer from it.<span class=$\nu(p)$ as a function of p" />

Note that the paper by D. Viswanath does (briefly) discuss a biased version (see, e.g., Figure 5); however, the recurrence considered there is of the form $F_{n} = \varepsilon_n F_{n-1} + \varepsilon_n' F_{n-2}$ where $\varepsilon'_n,\varepsilon_n$ are i.i.d. The result is the same (because of the absolute values) when $p=1/2$, but it is not the case for $p\neq 1/2$.

  • 3
    $\begingroup$ The paper How do random Fibonacci sequences grow? has some results on this problem and a nonlinear generalization. A preprint is also available at arXiv:math/0611860 in case you don't have access to PTRF. $\endgroup$ – HMPanzo Nov 8 '20 at 2:40
  • $\begingroup$ Thanks -- Based on the abstract it looks very relevant. $\endgroup$ – Clement C. Nov 8 '20 at 2:43
  • $\begingroup$ Mmmh. That made me realize I made a mistake in my simulations and attempts, so even better... $\endgroup$ – Clement C. Nov 8 '20 at 2:57
  • $\begingroup$ @HMPanzo If you want to make this comment an answer, I definitely would upvote it. This would be a very good reference to have archived permanently here. $\endgroup$ – Clement C. Nov 10 '20 at 18:26

This example is discussed in my 1990 PhD thesis, where is it is shown that $\nu(p)$ is a real analytic function of $p$. The thesis was written in Hebrew, but this result was generalized in two papers [1], [2]. Note that the existence of the limit you call the Viswanath constant (and more generally, $\nu(p)$) is an immediate consequence of the Furstenberg-Kesten Theorem [3] on the existence of the top Lyapunov exponent for random matrix products. This is because the vector $(F_n,F_{n+1})$ is obtained by multiplying $(F_{n-1},F_n)$ by a random matrix that takes two possible values.

[1] Peres, Yuval Analytic dependence of Lyapunov exponents on transition probabilities. Lyapunov exponents (Oberwolfach, 1990), 64–80, Lecture Notes in Math., 1486, Springer, Berlin, 1991.

[2] Peres, Yuval Domains of analytic continuation for the top Lyapunov exponent. Ann. Inst. H. Poincaré Probab. Statist. 28 (1992), no. 1, 131–148. (Reviewer: Philippe Bougerol) http://www.numdam.org/article/AIHPB_1992__28_1_131_0.pdf

[3] Furstenberg, Harry, and Harry Kesten. "Products of random matrices." The Annals of Mathematical Statistics 31, no. 2 (1960): 457-469.


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.