This is the typical drunk problem wherein the person is confined to moving either to the North, South, East, or West but never diagonally with just one step. A step has a length $L$. What is the probability that the drunk will never leave a circle of radius $2L$ after $N$ steps?

Obviously, the probability is zero for $N=1$ and $N=2$. For $N=3$, I got it to be $3/4$ although I am not sure whether this is correct. For $N>3$, I am just lost.

  • 1
    $\begingroup$ This is a Markov process with $13+1$ states. $\endgroup$ – Hagen von Eitzen Jan 28 '14 at 7:48
  • $\begingroup$ @Hagen von Eitzen: You can cut it down to 5 states by symmetry, and to 2 states (one of which is absorbing) if you look at the position after an odd number of steps. $\endgroup$ – Henry Jan 28 '14 at 7:59

After an odd number of steps, you are either at a point $(0,\pm 1)$, $(\pm 1,0)$, or outside the circle. You can only cross the circle on an odd step. If you start at one of those $(0,\pm 1)$, $(\pm 1,0)$ points, then you have a probability $\frac14 \times 1 + \frac12 \times \frac12 + \frac14 \times \frac14 = \frac{9}{16}$ of not leaving the circle in the next two steps.

After $N=1$ step, the probability of not having left the circle is, as you say, $1$. So for $N=3$ it is $\frac{9}{16}$, and you then keep multiplying by $\frac{9}{16}$ every two steps.

So after $N$ steps the probability of not having left the circle is $\left(\frac{9}{16}\right)^{\lfloor(N-1)/2\rfloor}$ for positive $N$.


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.