3
$\begingroup$

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.

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

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – James Apr 26 '15 at 13:45
  • $\begingroup$ @EdJar Remember $\mu > 0 \implies \sqrt{1+4\mu} > 1 \implies \frac{1+\sqrt{1+4\mu}}{2} > 1$. $\endgroup$ – achille hui Apr 26 '15 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.