6

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

hobbs
  • 290
Anwesh saha
  • 61
  • 3
    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? – user2974951 Aug 07 '23 at 10:36
  • 3
    The question cannot be answered unless you define what "escaping" means. – Tim Aug 07 '23 at 10:39
  • 1
    @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? – Anwesh saha Aug 07 '23 at 10:58
  • 1
    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." – R.. GitHub STOP HELPING ICE Aug 07 '23 at 19:16
  • I submitted an edit fixing the quotation from the book. The problem statement in the book doesn't define "escape" specifically, but from the solution it's clear that P(escape) is the limit of P(x > 0) as t→∞, which does exist. – hobbs Aug 07 '23 at 20:34
  • @hobbs your edit changes the quote. I am not sure whether that is a good thing to do. It would be better to instead clarify the problem outside the quote and keep the quote itselve intact. – Sextus Empiricus Aug 07 '23 at 21:14
  • 1
    @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. – hobbs Aug 07 '23 at 21:47
  • @hobbs Ah, in that case it makes sense. So, you are 'correcting a quote that was not correctly quoted', instead of 'correcting a quote that was not correct'. (still, it doesn't change that the sentence was not grammatical correct) – Sextus Empiricus Aug 07 '23 at 23:01

1 Answers1

7

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(-(2ps1-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

Sextus Empiricus
  • 77,915