Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 15 down vote accepted

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.

share|improve this answer
1  
@Chris: +1 for the simplifications to the obvious, more detailed, proof. –  Did Feb 15 '11 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 '11 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 '11 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 '11 at 18:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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