6
$\begingroup$

I came across the following question in Fifty Challenging Problems in Probability with Solutions by Frederick Mosteller in page no. $51:$

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 $\frac{2}{3}$, of a step toward the cliff $\frac{1}{3}$. What is his chance of escaping the cliff?

My question is, can the drunk man really "escape"? The man will always have a non-zero probability of returning to the starting point, albeit $0$.

$\endgroup$
8
  • 3
    $\begingroup$ Well, how do you define "escaped"? Is there a certain limit after which you can say he escaped and the game is finished, say 10 steps away from the cliff? Or is this drunk potentially taking infinite steps away? $\endgroup$ Commented Aug 7, 2023 at 10:36
  • 3
    $\begingroup$ The question cannot be answered unless you define what "escaping" means. $\endgroup$
    – Tim
    Commented Aug 7, 2023 at 10:39
  • 1
    $\begingroup$ @user2974951 I have added the link to the source (P.51). The author has calculated the probability for different scenarios (and not just p = 2/3). He gets 1 and p/1-p as a solution. I still find it challenging to understand how certain scenarios will have 1 as the answer and specific scenarios as the latter. Can we say with conviction that the drunkard falls from a cliff? $\endgroup$ Commented Aug 7, 2023 at 10:58
  • 1
    $\begingroup$ This sentence is ungrammatical and seems to have a typo: "At any step, his probability of taking a step away is 3, of a step toward the cliff." $\endgroup$ Commented Aug 7, 2023 at 19:16
  • 1
    $\begingroup$ @SextusEmpiricus I found the book and changed the quote to correctly quote the book. I think that's fair game in this case. The previous version basically amounts to a typo. $\endgroup$
    – hobbs
    Commented Aug 7, 2023 at 21:47

1 Answer 1

7
$\begingroup$

My question is, can the drunk man really "escape"? The man will always have a non-zero probability of returning to the starting point, albeit $0$.

Your random walk with unequal probability can be approximated as a random walk with drift. For this it is possible to have a non-zero escape probability.

You can compare this with the situation from the question Who was the first person to prove the straight line cross probability for a Brownian motion? , which is about a continuous random walk.

The density for the position of the random walk can be considered as a difference between two Gaussian distributions.

$$ W(x_0,x,t) = \frac{ e^{-\frac{(x-x_0-ct)^2}{4Dt}} - \left(e^{{-c x_0/D}}\right) e^{-\frac{(x+x_0-ct)^2}{4Dt}} }{ \sqrt{4\pi D t}}$$

Where $x_0$ is the initial position, $t$ the time, $c$ the drift (relating to the average step direction) and $D$ the diffusion (relating to the variance in the step direction/sizes).

  • One part relates to the random walk without the cliff
  • The other part relates to a correction term that involves the paths that have been ignored by the first distribution and may have crossed the boundary. (These paths are a reflection of the paths from the first part)

This gives an image like this:

illustration as diffusion in force field

The subtracted/reflected part is only a fraction $e^{{-c x_0/D}}$ of the total. So there is a non-zero escape possibility if the drift is positive.


For your case with binary steps there you could approximate it by approximating the binary steps with a normal distribution. Take $x_0 = 1$, $c = 2p-1$ and $D = \sqrt{p(1-p)}$ making the escape probability approximately $e^{-(2p-1)/\sqrt{p(1-p)}}$.

A simulation shows a reasonable agreement.

comparison

tm = 500
p = 2/3

sim = function(p, tm) {
   steps = rbinom(tm,1,p)*2-1
   position = c(1+cumsum(steps),0)
   hit = which(position == 0)
   return(hit[1])
}

plot(-100,-100,xlim=c(0,1),ylim=c(0,1),
     xlab = "positive step probability",
     ylab = "escape probability") 

### plot lines for computation 
ps1 = seq(0.5,0.9,0.01)
lines(ps1,1-exp(-(2*ps1-1)/sqrt(ps1*(1-ps1))),pch=2)

ps2 = seq(0,0.5,0.01)
lines(ps2,ps2*0,pch=2)

### plot points for simulations 
ps = seq(0.3,0.95,0.025)
for (p in ps) {
   k = replicate(3*10^4, sim(p,tm))
   points(p,mean(k==tm+1),pch = 21, bg=0)
}

legend(0,1, c("simulations", "approximation formula"), pch = c(1,NA), lty = c(NA, 1))

Possibly a more direct computation, leading to p/(1-p) as in your comments, could be made by considering the probability based on an iterative scheme. E.g. considering the probabilities, $p(x_1 \to x_2)$, to reach position $x_2$ from $x_1$ and relate those with each other.

Edit: today I came across an old related question Amoeba Interview Question

The solution approach is similar. We can consider the probability of getting to the cliff as the probability that the population of amoeba's dies out. Then the solution can be computed as

$$P_{cliff} = (1-p) + p P_{cliff}^2$$

leading to one of the roots of the quadratic curve as solution

$$P_{cliff} = \frac{1}{2p} - \frac{\sqrt{1-4p(1-p)}}{2p}$$

Indeed the match is better, when we add the lines

lines(ps1, 1-1/2/ps1 + sqrt(1-4*ps1*(1-ps1))/2/ps1, col = 2, lty = 2)

legend(0,0.8, c("exact formula"), lty = 1, col = 2)

then the image becomes

improvement

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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