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
Exact probability for the distance after $t$ steps
we can use a method from G. A. Whitmore & V. Seshadri to derive the first passage time of a Wiener process (described in Deriving Inverse Gaussian as First Passage Time of Wiener Process) to compute an exact distribution.
Let $k(t)$ be the position of the drunk man after $t$ steps, $k(0) = 1$, the absorbing boundary is at $k=0$, the man takes steps forward with probabability $p$ and backwards with probabability $q=1-p$, and for simplicity we consider even numbers of steps $t$.
For a given path that the drunk man takes he took $x=\frac{t+k(t)}{2}$ steps forward and $y=\frac{t-k(t)}{2}$ steps backwards, and the particular probability for that path is $p^xq^y$.
The number of paths that lead to position $k(t)$ is equal to ${{t}\choose{x}} - {{t}\choose{x+1}}$ if $x<t$ or $1$ if $x=1$. This can be argued based on a reflection principle. One can imagine a random walk without absorbing boundary at zero, and consider the paths that ended up at zero or below.
For every such path that ended up below zero, we can imagine a reflected path that ended up above zero.
Such reflected paths are all the possible paths that ended up above zero, but hit the zero in between time $0$ and $t$, thus out of the ${{t}\choose{x}}$ paths that end up in $x$ if there is no absorbing boundary, ${{t}\choose{x+1}}$ are paths that can be reflected.
Thus, the probability is
$$P(K = k|t) = \left[{{t}\choose{x}} - {{t}\choose{x+1}}\right] p^xq^y$$
where $x=\frac{t+k}{2}$ steps and $y=\frac{t-k}{2}$
If we compute the integral you get
$$P(K >0 |t) = S(t+1,2t,p) - \frac{q}{p} S(t+2,2t,p)$$
where $S(x,t,p)$ is the survival function of the binomial distribution.
In the limit $t \to \infty$ we get $$\lim_{t\to\infty} P(K >0 |t) = 1-\frac{q}{p} = 2 - \frac{1}{p}$$ this is the same as the earlier computed $1-\frac{1}{2p} + \frac{\sqrt{1-4p(1-p)}}{2p}$ where the term in the root could have been simplified as $(1-2p)^2$.
