I have a random walk with the following rules:

  • It starts at 2
  • At each step it goes up by 1 with chance .4, down by one with chance .4 and up by 2 with chance .2
  • The walk ends if it reaches 0

I want to know two things...

  1. Firstly is this guaranteed to terminate at some point - I believe it is but confirmation would be nice. If not can a probability be given to it not finishing?
  2. What is the probability of the walk having a given maximum value (eg what is the probability of it getting to 10 but no higher before terminating at zero).

And just so you know I used to study maths at university but that was a while ago now so best to assume that I know basic stuff but try not to assume too much knowledge on my part in an answer. :) I also was never great at statistics. ;-)

I tried solving the problem using a difference equation but I got stuck trying that. I'm not sure that was the right way to go really...

  • $\begingroup$ Regarding your first question: What do you now about the time-to-ruin of a "standard" biased random walk with probability of an up move of $p > 1/2$? Can you make a simple comparison of your walk to that? Conclusion? $\endgroup$ – cardinal Dec 28 '11 at 23:30
  • $\begingroup$ Hmm... Since there is a higher probability of going up than down (0.6 to 0.4), it seems that in the long run, it will tend to increase. That's all I can figure out. Nice question! Also, what do you mean by lower bounded here? $\endgroup$ – itdoesntwork Dec 28 '11 at 23:30
  • 1
    $\begingroup$ He means absorption at 0. $\endgroup$ – gnometorule Dec 28 '11 at 23:34
  • $\begingroup$ @gnometorule: I did mean that. Its a while since I last did this stuff and I count myself lucky to have remembered the name "random walk" at all. ;-) $\endgroup$ – Chris Dec 30 '11 at 9:01

I can handle part 1. I'm thinking about part 2, but it looks quite difficult in general - I'll edit this answer if I figure it out.

For part 1, look at the probability of eventually going one space left. Call this P. Then the probability of eventually going two spaces left is just going to be the probability of going one space left, and then going another space left: $P^2$. Similarly, the probability of going three squares left is $P^3$, et cetera...

Now, directly from the random walk's parameters, we have:


Why? Well, we have a .4 chance of going left immediately, in which case we're finished ($.4$). We have a .4 chance of starting by going right, in which case we have to work our way left two spaces eventually ($.4P^2$). And we have a .2 chance of starting by going right two spaces, in which case we have to go left three spaces eventually ($.2P^3$).

WolframAlpha tells us that of the three solutions to this equation, one is negative and the other two are P=1 and P=~0.561553.

The negative solution is obviously wrong. The P=1 solution is non-obviously wrong, but since your random walk tends to increase, there's a positive probability that it will just spiral towards infinity. Therefore P is about 0.561553, and the probability of finishing from the starting point of 2 is $0.561553^2$ which is about $0.315341$.

  • $\begingroup$ The equation has higher order terms. This gets more convoluted looking first hit times later. I can't give the proper solution myself, but am fairly certain this neglects terms we can't neglect. This is just the probability to go 1 down in no more than 3 steps. $\endgroup$ – gnometorule Dec 29 '11 at 0:26
  • $\begingroup$ Unless I made a mistake somewhere, I'm fairly certain that the formula I give is the probability of going down 1 step eventually, not just in the next 3 steps. I've just edited to clarify how I got the cubic equation in the middle. $\endgroup$ – Lopsy Dec 29 '11 at 2:01
  • $\begingroup$ @gnometorule, the argument leading to the third degree equation in $P$ is right. The key word is eventually. $\endgroup$ – Did Dec 29 '11 at 10:13
  • $\begingroup$ @Didier: You're probably right, and it's embarrassing for personal reasons. $\endgroup$ – gnometorule Dec 29 '11 at 15:26
  • $\begingroup$ Thanks. That's the sort of thing I was wanting. :) I was just going about it all wrong. Part 2 is of less interest to me if there is such a high chance of never reaching zero anyway so don't worry too much about part 2. :) $\endgroup$ – Chris Dec 30 '11 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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