# Zeroes of the random Fibonacci sequence

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?

-
In Wiki, the first $\pm$ is missing (in the formula for $X_n$)? –  Mark Sapir Aug 21 '11 at 18:47
Oh yeah, sorry, doesn't really matter as this induces a global random sign change. –  JSE Aug 21 '11 at 19:13
Perhaps you would like to include the observation that the nth term is zero implies n is a multiple of 3? Gerhard "Ask Me About System Design" Paseman, 2011.08.21 –  Gerhard Paseman Aug 21 '11 at 19:29
Further, the probability of x_{n+d} is zero is bounded below by the probability that x_n is 0 times the probability that y_d is zero for d small and d is the smallest index for which y_k is a general fibonacci sequence and y_d is zero. Perhaps this can be used for a quick and rough estimate. Gerhard "Ask Me About System Design" Paseman, 2011.08.21 –  Gerhard Paseman Aug 21 '11 at 19:38

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.

-
The paper link is here aero.tamu.edu/sites/default/files/faculty/kalmarnagy/… –  j.c. Aug 21 '11 at 23:32
Do you mean the probability that $X_{3n}=0$ is bounded above by $(27/32)^n$? I observed a base of about $e^{-0.0764}\approx0.926$, and if I'm not miscalculating, your bound gives a base of $(27/32)^{1/3}\approx0.945$ which is rather close. –  j.c. Aug 21 '11 at 23:44
Ah, yes, I meant $X_{3n}$. –  Gjergji Zaimi Aug 21 '11 at 23:51
The upper estimate can also be rewritten by replacing 3n choose n by 3((3n-1) choose (n-1)), which makes for a nicer comparison with the lower bound. Gerhard "Ask Me About System Design" Paseman, 2011.08.21 –  Gerhard Paseman Aug 22 '11 at 4:24
I might update to clarify this, but I was mainly concerned with asymptotics and I forgot to mention that the upper bound is valid up to a constant factor. According to this answer here that constant is $\approx (3+\sqrt{5})/4$. mathoverflow.net/questions/63789/… –  Gjergji Zaimi Aug 31 '11 at 19:57

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

-

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 expoenential fit is something like $e^{-1.18-0.0764n}$.

The probability density function for the number of zeroes in each sequence also seems to decay exponentially (the y-axis ought to read "Probabilty 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"}]

-
Isn't exponential decay of probability obvious given that the sequence exponentially growth a.s. ? –  Mark Sapir Aug 21 '11 at 20:49
Is that easy to see? It certainly sounds reasonable. –  j.c. Aug 21 '11 at 22:19
I would have said "it's the obvious guess" but I don't see that it literally follows. –  JSE Aug 21 '11 at 23:16