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?



A random walk on natural numbers
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.


