4

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?

flag
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 2011 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 2011 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 2011 at 0:25

1 Answer

15

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.

link|flag
1 
 @Chris: +1 for the simplifications to the obvious, more detailed, proof. – Didier Piau Feb 15 2011 at 17:57
Thanks Chris. There is still a minor point: not every decrease is by a factor of 2, since with probability 1/4, there is no decrease. – Hej Feb 15 2011 at 18:21
3 
 @Hej: as I said at the start, I'm ignoring the possibility of not moving. In detail: The probability of your walk eventually staying in one nonzero place for ever is zero, so we can define a new walk which is the subsequence of your walk obtained by ommiting every step where it didn't move. Then the new walk reaches zero iff the old walk does, and the new walk has probabilities 5/9 of decrease and 4/9 of increase. My argument applies to this new walk throughout. – Chris Eagle Feb 15 2011 at 18:45
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 2011 at 18:46

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.