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$?



Zeroes of the random Fibonacci sequence
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](https://mathoverflow.net/questions/1960/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.


