Return to Answer

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.

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.

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

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.

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: In fact this shows that the probability of $X_{3n}=0$ can be computed exactly, it is $2^{1-3n}\binom{3n-1}{n-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$.