# Probability of asymmetric random walk returning to the origin

Consider the random walk $S_n$ given by $S_{n+1} = \left\{ \begin{array}{lr} S_n+2 & with & probability & p\\ S_n - 1 & 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.

• You may want to have a look at this math.stackexchange.com/a/65050/233398 -- about generating functions. – Alexey Burdin Apr 26 '15 at 2:05
• There is also the possibility to solve this using martingale theory. If you are interested, just ping me. – saz Apr 26 '15 at 8:39
• @saz, I would be interested in the alternate solution! – sebhofer Mar 1 '16 at 18:16

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.
• This is very helpful. Are you sure $B=0$? You say the second root is <-1 but that doesn't seem to account for the fact that it's divided by 2. – James Apr 26 '15 at 13:45
• @EdJar Remember $\mu > 0 \implies \sqrt{1+4\mu} > 1 \implies \frac{1+\sqrt{1+4\mu}}{2} > 1$. – achille hui Apr 26 '15 at 13:48