# (Random Walk) Probability of Returning to Origin

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?

• 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. – Did May 9 '16 at 20:03
• 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. – Did May 9 '16 at 20:06
• @Did, the recurrence should read $p_0= p\cdot p_1 + (1-p)p_{-1}$. – zhoraster May 9 '16 at 20:07
• @zhoraster Indeed, thanks. – Did May 9 '16 at 20:08
• That is a much easier method, thanks for bringing it up. – 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.
• Aha, stupid of me to miss that. The series, iff $p > \frac{1}{2}$, indeed converges to the right number now! – Tiamo P. May 9 '16 at 20:21