Zeroes of the random Fibonacci sequence

Question

Let $X_n$ be the "random Fibonacci sequence," defined as follows:

$X_0 = 0, X_1 = 1$;

$X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips.

It is known that $|X_n|$ almost surely grows exponentially by a (much more general) theorem of Furstenberg and Kesten about random matrix products: the base of the exponent was determined explicitly by Viswanath to be $1.13\ldots$

I am not too proud to say that I learned all this from Wikipedia:

http://en.wikipedia.org/wiki/Random_Fibonacci_sequence

What I did not learn from Wikipedia, or any of the references I gathered therefrom, was:

Question: what, if anything, do we know about the probability that $X_n = 0$, as a function of $n$?

Answer 1

In response to Mark's comment, it is possible to determine that the probability of $X_n=0$ decays exponentially directly, and this is in fact easier than the theorems about the growth of these random sequences.

Since we only care about testing if the sequence becomes zero, symmetry implies that we might as well reduce to the case $X_n=|X_{n-1}\pm X_{n-2}|$. If you see the paper "The random Fibonacci recurrence and the visible points of the plane" by T. Kalmar-Nagy, these sequences are in bijection with random walks on an infinite directed graph which looks like a trivalent tree with added parallel edges at every level.

The probability you ask for can be translated into the question of the probability that a random walk in our graph returns to the origin after $n$ steps. There is a lot of machinery available for studying random walks on highly symmetric graphs (in this case we don't have a Cayley graph, but it's really close). I did the following simple estimate: The number of walks of length $3n$ starting from the origin is $2^{3n}$. For such a path to return to the origin exactly a third of its edges are directed south-west (I'm referring to the fig. 4 on page 4 of the paper I linked to). So the numbers of paths of length $3n$ with both endpoints at the origin is at most $\binom{3n}{n}\sim (27/4)^n$. So in particular the probability that $X_{3n}=0$ is bounded above by $(27/32)^n$.

Added: Here's how one can get a lower bound as well. It is not hard to see that walks of length $3n$ in our graph are in bijection with sequences $\lbrace a_1,a_2,\dots,a_{3n}\rbrace$ which satisfy $a_i\in \lbrace 1,-\frac{1}{2}\rbrace$ and $$a_1+\cdots+a_{3n}= 0$$ $$a_1+\cdots+a_m\geq 0$$ for all $1\le m\le 3n$, and if $a_1+\cdots+a_m=\frac{1}{2}$ then $a_{m+1}=-\frac{1}{2}$. Enumerating these sequences exactly can get a bit tricky but there is a particularly nice subset if we restrict to the stronger condition $$a_1+\cdots+a_m > 1$$ for all $2\le m\le 3n-3$. Then we can enumerate these as Dyck paths on rectangles. The formula from that thread gives us $\frac{1}{3n-3}\binom{3n-3}{n-1}$. So to summarize we have $$\frac{1}{(3n-3)2^{3n}}\binom{3n-3}{n-1}\le P(X_{3n}=0)\le \frac{1}{2^{3n}}\binom{3n}{n}$$ and in particular $$\lim_{n\to \infty} \sqrt[n]{P(X_{3n}=0)}=\frac{27}{32}$$ which matches the experimental data in jc's answer.

Answer 2

First of all, it is somewhat misleading to attribute the claim concerning exponential growth to Furstenberg and Kesten. What they proved (in 1960) is that for partial products of a random stationary sequence of matrices there exists almost surely an exponential rate of growth. However, it does not exclude possibility that this growth rate is zero. Its positivity for i.i.d. sequences was proved (under reasonable irreducubility conditions) by Furstenberg in 1963.

Now to your question. The reduction to matrix products consists in observing that $$ \left( X_{n+1} \atop X_n \right) = \left( 1 \;\pm 1 \atop1\;\;\;\;\;\ 0 \right) \left( X_n \atop X_{n-1} \right) \;, $$ whence $$ \left( X_{n+1} \atop X_n \right) = B_n \left( 1 \atop 0 \right) \;, $$ where $$ B_n = A_n A_{n-1} \dots A_1 $$ is the product of i.i.d. matrices $A_i$ which are either $M=\left( 1 \;1 \atop1\; 0 \right)$ or $M'=\left( 1 \;-1 \atop1\;\;\; 0 \right)$ with equal probabilities 1/2 (as explained by JSE, one can omit the first $\pm$ in the recurrence relation). Therefore, $X_n=0$ iff $B_n$ is an upper triangular matrix with $\pm 1$ on the diagonal. The Schreier graph of the quotient of $GL(2,\mathbb Z)$ by the group of such triangular matrices is non-amenable, whence one can deduce exponential decay of the return probabilities.

PS The answer to Mark's question is NO. The reason is that there exist amenable groups (e.g., the higher dimensional lamplighter groups), for which the linear rate of escape of the simple random walk is strictly positive (which is analogous to positivity of the exponent for matrix products), but nonetheless the probability of returning to zero decays subexponentially (because of amenability).

Answer 3

The results from considering $10^6$ pseudorandom $X_n$ for $n\leq 200$ suggest that the probability of being zero might decay exponentially:

The best exponential fit is something like $e^{-1.18-0.0764n}$. The base of the exponential growth is $e^{-.0764}\approx0.926$ which is consistent with the upper bound from Gjergji Zaimi's answer of $(27/32)^{1/3}\approx0.945$.

The probability density function for the number of zeroes in each sequence also seems to decay exponentially (the y-axis ought to read "Probability of having $z$ zeroes in $\{X_i\}_{i=0}^{200}$", and this plot really should start at $z=1$, rather than $z=0$):

The best exponential fit is something like $0.618e^{-0.481z}$.

These were produced with the following Mathematica code (with apologies to Mathworld's page):

max = 200;
max2 = 10^6;
stats = Table[m = #[[1, 1]] & /@ FoldList[Dot, IdentityMatrix[2], {{0, 1}, {1, #}} & /@ ((-1)^Table[Random[Integer], {max}])];
Flatten[Position[m, 0], 1], {max2}]; 
numstats = Tally[Table[Length[stats[[i]]], {i, max2}]];
numstats2 = Table[{numstats[[i, 1]], numstats[[i, 2]]/max2}, {i, Length[numstats]}];
ListLogPlot[numstats2, AxesLabel -> {"z", "probability of z zeros in \!\(\*SubscriptBox[\(X\), \(0\)]\) to \\!\(\*SubscriptBox[\(X\), \(200\)]\)"}]
fstats = Tally[Flatten[stats, 1]];
fstats2 = Table[{fstats[[i, 1]] - 2, fstats[[i, 2]]/max2}, {i, Length[fstats]}];
ListLogPlot[fstats2, AxesLabel -> {"n", "probability of \!\(\*SubscriptBox[\(X\), \(n\)]\) being zero"}]