# Random walks with exponential decreasing steps

Let $g$ be the golden number (or another algebraic integer in $(0,1)$ that fullfills an equation with coefficients $\pm 1$). Consider the random walk on $\mathbb{R}$ starting with $0$ and walking $g^{n}$ with probability $1/2$ left or right in step $n+1$. What is the probability to return to $0$ exactly $m$-times. Here $m$ maybe $0$ and $\infty$ as well. If $g$ ist not as described the walk will of course not return at all.

• What polynomials with coefficients $\pm 1$ are there which have $g$ as a root? Is it necessary that the degree is $3n+2$ and the coefficients satisfy $a_{3m}=-a_{3m+1}=-a_{3m+2}$ for all $0\leq m\leq n$? If so, then the random walk can only be at zero at times which are 0 mod 3, and furthermore if it is not at zero at some time which is 0 mode 3, then it will never hit 0 again. In that case the probability of being at zero at time $3n$ is $(1/4)^n$ and the total number of visits to zero (including at time 0) has geometric distribution with mean $4/3$. – James Martin Nov 7 '14 at 19:51

## 1 Answer

In the case of the golden number $g = (\sqrt{5}-1)/2$, we have $g^n = (-1)^n (F_{n-1} - F_n g)$ where $F_n$ is the $n$'th Fibonacci number. Let $a_i, i=0,1,2,\ldots$ be $+1$ if the $i+1$'th step is to the right, $-1$ if it is to the left. Then we return to the origin after $n$ steps iff $\sum_{i=0}^{n-1} a_i F_i = 0$ and $\sum_{i=0}^{n-1} a_i F_{i-1} = 0$.

Note that $\sum_{i=0}^{n-1} a_i F_i \equiv 1 \mod 2$ if $n \equiv 2 \mod 3$ and $\sum_{i=0}^{n-1} a_i F_{i-1} \equiv 1 \mod 2$ if $n \equiv 1 \mod 3$, so the only possibilities for return are with $n$ divisible by $3$. Moreover, if $a_{n-3}, a_{n-2},a_{n-1}$ are not either $[1,1,-1]$ or $[-1,-1,1]$ then we have \eqalign{\left| \sum_{i=0}^{n-1} a_i F_i \right| &\ge F_{n-1} - F_{n-2} + F_{n-3} - \sum_{i=0}^{n-4} F_i \cr &= -1-\dfrac{ \sqrt {5}-1 }{2} \left( \dfrac{1-\sqrt {5}}{2} \right) ^{n-3}+ \dfrac{ \sqrt {5}+1}{2} \left( \dfrac{\sqrt {5 }+1}{2} \right) ^{n-3}\cr &> 0 \ \text{for}\ n \ge 4} So the only ways to ever return to the origin are to return to the origin after every $3$ steps, each three steps being either $+,-,-$ or $-,+,+$. The probability of having exactly $m$ returns to the origin is then the probability that the first $3m$ steps follow this pattern but the next $3$ do not, thus $3 \times 4^{-m-1}$.

EDIT: A simpler argument in the case of the golden number:

Note that if $(a_0, a_1, a_2)$ is not $(1,-1,-1)$ or $(-1,1,1)$, $$|a_0 + a_1 g + a_2 g^2| \ge 3 - \sqrt{5} > g = \sum_{n=3}^\infty g^n$$ So if you don't return to the origin after the first $3$ steps, you are too far away to ever return. Similarly for $(a_{3n}, a_{3n+1}, a_{3n+2})$ where $\sum_{i=0}^{3n-1} a_i g^i = 0$...

A similar argument works for the next case, where $g$ is the real root (approximately $0.5436890127$) of $X^3 + X^2 + X - 1$. If $(a_0,a_1,a_2,a_3)$ is not $(1,-1,-1,-1)$ or $(-1,1,1,1)$, $$|a_0 + a_1 g + a_2 g^2 + a_3 g^3| \ge 1 - g - g^2 + g^3 > \dfrac{g^4}{1-g} = \sum_{i=4}^\infty g^i$$ so the only way to ever return to the origin is to return every $4$ steps.

However, this argument won't work for the positive root (approximately $0.8483748957$) of $X^4 + X^3 + X^2 - X - 1$. For this case, is it possible to return to the origin without returning after the first $5$ steps?

• I think you give the probability to return consecutive to the origin (every time it is possible at all), but what is probability if You allow the walk not to return for some time? – Jörg Neunhäuserer Nov 9 '14 at 11:51
• If the walk ever fails to return when $n$ is a multiple of $3$, then it will never return. – Robert Israel Nov 9 '14 at 20:21
• I think that is not true. Walk RRLLLL (R= Right, L=Left) with the golden mean. You will not return in 3 but in 6 steps. – Jörg Neunhäuserer Nov 10 '14 at 14:35
• No, you won't. $1 + g - g^2 - g^3 - g^4 - g^5 = 3 - \sqrt{5} > 0$. – Robert Israel Nov 10 '14 at 16:16