Probability of asymmetric random walk returning to the origin 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.
 A: 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


*

*$\color{blue}{[1]}$ This is a hand waving argument, feel free to justify this rigorously.

