How do random Fibonacci sequences grow?

Abstract

We study two kinds of random Fibonacci sequences defined by $F_1=F_2=1$ and for $n\ge 1$, $F_{n+2}=F_{n+1}\pm F_n$ (linear case) or $F_{n+2}=|F_{n+1}\pm F_n|$ (non-linear case), where each sign is independent and either + with probability $p$ or - with probability $1-p$ ($0<p\le 1$). Our main result is that the exponential growth of $F_n$ for $0<p\le 1$ (linear case) or for $1/3\le p\le 1$ (non-linear case) is almost surely given by $${\int }_0^{\infty }\log xd{\nu }_{\alpha }(x),$$ where $\alpha$ is an explicit function of $p$ depending on the case we consider, and ${\nu }_{\alpha }$ is an explicit probability distribution on $\RR_+$ defined inductively on Stern-Brocot intervals. In the non-linear case, the largest Lyapunov exponent is not an analytic function of $p$, since we prove that it is equal to zero for $0<p\le 1/3$. We also give some results about the variations of the largest Lyapunov exponent, and provide a formula for its derivative.