I want to find out the probability that a 1-dimensional asymmetric random walk, which steps to the right with probability $p > \frac{1}{2}$ and to the left with probability $1-p$, ever returns to the origin.

I tried to solve this by defining the probability of return to the origin after exactly $n$ steps, and taking the summation over these probabilities. This led me to

$$ \mathbb{P}(\text{"return to origin"}) = \sum_{n=0}^{\infty} \binom{2n}{n} p^{n} (1-p)^{n}$$

However, for any value for $p$ greater than $\frac{1}{2}$, the series converges to a number greater than 1. (Tested with WolframAlpha.) What am I doing wrong? How can I solve this problem?

  • 1
    $\begingroup$ You are confusing the probability to return at the origin with the mean number of times one visits the origin. To compute $p_0=P_0(T_0<\infty)$, use the Markov property after one step, thus $p_0=pp_1+(1-p)p_{-1}$ where $p_x=P_x(T_0<\infty)$. Now, $p_{-1}=1$ should be clear and to compute $p_1$, you might want to use the Markov property after one step once more. $\endgroup$ – Did May 9 '16 at 20:03
  • 3
    $\begingroup$ Another option is to note that the RHS in your post is $1/(1-p_0)$ hence recognizing $\sum\limits_{n\geqslant0}{2n\choose n}x^n$ for $1/\sqrt{1-4x}$ yields $p_0=2(1-p)$ right away. $\endgroup$ – Did May 9 '16 at 20:06
  • $\begingroup$ @Did, the recurrence should read $p_0= p\cdot p_1 + (1-p)p_{-1}$. $\endgroup$ – zhoraster May 9 '16 at 20:07
  • $\begingroup$ @zhoraster Indeed, thanks. $\endgroup$ – Did May 9 '16 at 20:08
  • $\begingroup$ That is a much easier method, thanks for bringing it up. $\endgroup$ – Tiamo P. May 9 '16 at 20:22

What you're doing wrong is that you're double-counting those walks that return to the origin twice or more. Instead of $\binom{2n}{n}$, you may want to use the Catalan numbers to construct the number of paths that return to the origin for the first time after exactly $n$ steps.

  • $\begingroup$ Aha, stupid of me to miss that. The series, iff $p > \frac{1}{2}$, indeed converges to the right number now! $\endgroup$ – Tiamo P. May 9 '16 at 20:21

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.