4
$\begingroup$

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...

  • 0
    @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. ;-)2011-12-30

1 Answers 1

3

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:

$P=.4+.4P^2+.2P^3$

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$.

  • 0
    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. :)2011-12-30