# A random walk on natural numbers

We are taking a random walk on the set of natural numbers. If we are at $M$, then with probability 1/4, we stay at $M$, with probability 5/12 we move to some random number less than or equal to $M/2$, and with probability 1/3, we move to a random greater than $M$ but less than or equal to $(3M+1)/2$. Is it true that almost every random walk like this ends in 0?

-
This feels kind of related to the Collatz conjecture, especially since you have $(3M+1)/2$ instead of $3M/2$. I'm just wondering if this is where the question comes from. –  Michael Lugo Feb 15 '11 at 18:42
Interesting observation Michael. It seems that in the Collatz setting, the probabilities should be 1/2 and 1/2 (move to a larger number if odd, and to a smaller number if even). Do you know if Chris' argument can be applied to this scenario as well? –  Hej Feb 15 '11 at 19:46
@Hej: Indeed. A symmetric simple random walk $X_n$ on the integers achieves arbitrarily large positive and negative values almost surely. (I.e. $\limsup X_n = +\infty$ and $\liminf X_n = -\infty$ a.s.) –  Nate Eldredge Feb 16 '11 at 0:25

Yes. The possibility of staying at $M$ is irrelevant, so let's ignore it, so that the probability of an increase is 4/9 and the probability of a decrease is 5/9. For the moment, let's also ignore the actual sizes of these increases and decreases and let $X_n$ equal the total number of increases in the first n steps minus the total number of decreases in those steps. Then $X_n$ is a simple random walk on $\mathbb{Z}$ starting at 0 with probaility 4/9 of moving right and 5/9 of moving left. By a standard result on random walks on $\mathbb{Z}$, $X_n$ almost surely tends to $-\infty$. So for any k, we almost surely come to a point when we've had k more decreases than increases.
Going back to our original walk, every increase is by a factor of at most 2 and every decrease is by a factor of at least 2. So if we started at M and have had l increases and l+k decreases, then our current position is at most $2^l (1/2)^{l+k} M=(1/2)^k M$. So for k large enough, we must be at 0.
Alternatively, by the same standard results, a random walk on Z with probability 4/12 of moving right, 3/12 of staying still, and 5/12 of moving left will also almost surely tend to $-\infty$. –  Michael Lugo Feb 15 '11 at 18:46