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