Random Walk of a drunk man

Question

Problem Statement:

From where he stands, one step toward the cliff would send the drunken man over the edge. He takes random steps, either toward or away from the cliff. At any step his probability of taking a step away is 2/3, of a step toward the cliff 1/3. What is his chance of escaping the cliff?

My take:

Say the probability that he dies from where he stands right now is p. Then, he could comfortably make one step left and end his life with probability 1/3

Or he could take one step away and two step towards and boom...take two steps away and three steps toward...so on and so forth

Resulting in p= 1/3 + 2/3 * (1/3)^2 + (2/3)^2 * (1/3)^3 +....

Summing this infinite sequence gives me probability of dying as 3/7 (around 43%). I was rather puzzled when i learnt that the correct probability is 1/2. Cant figure out what are the other 7% ways for my drunken man to die which I missed above?

Answer 1

Note: not a compete solution as I haven't done the calculations, but I think if you do there should not be any problems

Let $p(i)$ be the probability of him falling when has a distance $i$ from the cliff.. We want $p(1)$

Clearly

$$p(1) = 1/3 + 2/3 p(2)$$ $$p(2) = 1/3p(1) + 2/3 p(3)$$

Which substituting gives

$$p(1) = 1/3 + 2/9p(1) + 4/9p(3)$$

Do it again substituting in $p(3) = 1/3p(2) + 2/3p(4)$ and try to get a relation where on the right hand side there is only $p(n)$; then let $n \to \infty$ and use the fact that $\lim_{n \to \infty} p(n) = 0$ to conclude

Answer 2

Before presenting a solution, I will say that your solution is wrong because it erroneously assumes that the man must go away from the cliff some number of steps and then proceed directly to the cliff, and otherwise he does not fall off. But on the contrary, he can turn around numerous times and still eventually fall off. Thus your result is a strict lower bound on the correct answer.

To correctly solve the problem, consider the sequence of hitting probabilities to hit $0$ before $n$ starting from a state $i$, where the probability to move right is $p$ and the probability to move left is $q=1-p$. Denote these probabilities by $h(i,n)$. We would like to compute $\lim_{n \to \infty} h(1,n)$.

By conditioning on the first step, we find that $h$ satisfies the equations:

\begin{align*} h(0,n) & = 1 \\ h(n,n) & = 0 \\ h(i,n) & = p h(i+1,n) + q h(i-1,n) \end{align*}

Consider the characteristic equation for this recurrence:

$$r = p r^2 + q \Leftrightarrow p r^2 - r + q = 0.$$

This has roots $r_1,r_2 = \frac{1 \pm \sqrt{1-4pq}}{2p}$. Since $pq=p(1-p) \in [0,1/4]$, these roots are real, and they are distinct if $p \neq 1/2$, as in your case.

Thus if $p \neq 1/2$ then we expect a solution of the form

$$h(i,n) = A_n r_1^i + B_n r_2^i.$$

Introducing the left boundary condition we get $h(0,n) = A_n + B_n = 1$. Introducing the right boundary condition we get $A_n r_1^n + B_2 r_2^n = 0$. Solving the system of linear equations we get $A_n = \frac{r_2^n}{r_2^n-r_1^n}$ and $B_n = \frac{-r_1^n}{r_2^n-r_1^n}$. So we have

$$h(i,n) = \frac{1}{r_2^n-r_1^n} \left ( r_2^n r_1^i - r_1^n r_2^i \right )$$

when $p \neq 1/2$.

I leave it to you now to compute $\lim_{n \to \infty} h(1,n)$ and plug in $p=2/3$.

Answer 3

Here is a proof that does not rely on solving recurrence equations.

Let $r$ denote the probability of hitting the cliff. Let $0,1,\dots$ denote the distance from the cliff. He starts at $1$.

If in the first step goes to $2$, then will hit the cliff if and only if will ever go back to $1$, and then will ever go to $0$. But probability of going back from $2$ to $1$ is the same as hitting cliff starting from $1$, that is $r$. Summarizing:

$$r= \frac 13 + \frac 23 r\times r,$$

or (writing $r=\frac 13 r + \frac23 r$):

$$ \frac 13 (r-1) = \frac 23 (r^2 -r).$$

That is, if $r\ne 1$, we have

$$ \frac 13 = \frac 23 r.$$

Or $r=\frac 12$.

It remains to show that $r\ne 1$. I'l allow myself to be sloppy and lazy, and will rely on the law of large numbers, which tells as that the position of this walk at time $n$ is of order $(\frac 23 - \frac 13)n$. In particular, the position tends to $+\infty$. If $r=1$, then by iterating, the probability of ever getting to $-1$ is also $1$, and the same for $-2$, etc. In particular, the path is unbounded from below. This contradicts the conclusion of the law of large numbers.