Consider the random walk $S_n$ given by
$
S_{n+1} = \left\{
\begin{array}{l}
S_n+2 & \text{with probability $p$}\\
S_n – 1 & \text{with probability $1-p$}
\end{array}
\right.
\
$
Assume that $S_0 = n >0 $. What is the probability of eventually reaching the the point $0$?
Seems that the probability for this must be less than one; since it is not symmetric, it is not guaranteed to reach the origin if $p>0.5$. It also seems like the positive starting value not being at the origin matters too, but I'm not sure how to compute the probability of eventually reaching the origin.
Best Answer
For any $n \ge 0$, let
$$f_n = {\bf Pr}\big[ S_0 =n \land \exists t > 0, S_t = 0 \big]$$ be the probability for a random walk start at location $n$ returns to origin in some finite time $t$.
Let $q = 1-p$ and $\displaystyle\;\mu = \frac{q}{p}\;$. It is easy to see $f_n$ satisfies a recurrence relation
$$f_n = \begin{cases} 1, & n = 0,\\ p f_{n+2} + q f_{n-1}, & n > 0 \end{cases}\tag{*1}$$ The corresponding characteristic equation $$\begin{align} p \lambda^2 + q\lambda^{-1} - 1 = 0 &\iff p(\lambda^2 - 1) - q(1-\lambda^{-1}) = 0\\ &\iff (\lambda^2 + \lambda - \mu)(\lambda - 1) = 0 \end{align} \tag{*2} $$ has three roots, $$1,\quad -\frac{1+\sqrt{1+4\mu}}{2}\quad\text{ and }\quad\frac{\sqrt{1+4\mu}-1}{2}$$ This implies $$f_n = A + B \left( -\frac{1+\sqrt{1+4\mu}}{2} \right)^n + C \left(\frac{\sqrt{1+4\mu}-1}{2}\right)^n$$ for some suitably chosen constants $A, B, C$.
Notice among the three roots, the $2^{nd}$ root is largest in magnitude and $< -1$. If $B \ne 0$, then $f_n$ will be negative for some sufficiently large $n$. This contradicts with the nature of $f_n$ being the probability of some event. This means $B = 0$. What happens to $A$ and $C$ depends on $\mu$.
If $\mu < 2$, the average drift of the random walk $r = 2p - q = p(2-\mu) > 0$.
For $t$ not too small, we can approximate $S_t$ by a normal distribution with mean $r t + n$ and standard derivation $\sigma = \sqrt{4p^2 + q - r^2} = 3\sqrt{pq}$. Within $K$ sigma, we have $$S_t > r t + n - K\sigma\sqrt{t} = r\left(\sqrt{t} - \frac{K\sigma}{2r}\right)^2 + n - \frac{K^2\sigma^2}{4r}$$ When $\displaystyle\;n > \frac{K^2\sigma^2}{4r}\;$, we expect the "return to origin" becomes a $K$ sigma event. This suggests$\color{blue}{^{[1]}}$ $$\lim_{n\to\infty} f_n = 0 \quad\implies\quad A = 0$$ Combine with the constraint $f_0 = 1$, we find $C = 1$ and $$f_n = \left(\frac{\sqrt{1+4\mu}-1}{2}\right)^n$$
If $\mu > 2$, the $3^{rd}$ root $\displaystyle\;\frac{\sqrt{1+4\mu} - 1}{2} > 1$. If $C \ne 0$, then $f_n$ will become unbounded for sufficiently large $n$. One again, this contradict with the nature of $f_n$ begin the probability of some event. This leads to $C = 0, A = 1$ and hence $f_n = 1$.
If $\mu = 2$, the characteristic equation $(*2)$ has a double root at $\lambda = 1$.
The general solution for $(*1)$ now takes the form $$f_n = A + B \left( -\frac{1+\sqrt{1+4\mu}}{2} \right)^n + C'n$$ One again, it is easy to see $C' = 0, A = 1$ and hence $f_n = 1$.
To summarize:
$$f_n = \begin{cases} \displaystyle\;\left(\frac{\sqrt{1+4\mu}-1}{2}\right)^n, & \mu < 2\\ 1, & \mu \ge 2 \end{cases}$$
Notes