# $N$-step one dimensional random walk that never returns to the origin.

I am looking for how to calculate the probability that an $N$-step one-dimensional random walk (on a lattice) never returns to its origin.

I found a reference that found that the probability of never returning to the origin is $|p-q|$, but this applies only to the case that $N\to \infty$; I thought that the probability that I am looking for in this problem is: $$1-\sum_{k=0}^n \frac{{ 2k \choose k}}{2k-1} (pq)^k$$

where $0<p=1-q<1$.

Obviously if the total number of steps $N$ is odd then with probability 1 we never return to the origin after $N$ steps.

So how to compute this probability for $N$ even?

Thanks.

N.B $$N=2n$$

• Feller's book deals with this (and many other questions of random walks). Also: you have a formula that looks as if it might be the right one for thing thing you're computing. What more do you want? – John Hughes Mar 16 '17 at 20:27
• Is it correct? I am not sure. – MathematicalPhysicist Mar 16 '17 at 20:28
• I have no idea --- why don't you explain how you derived it, or where you got it, and someone with more expertise than I have can help you out. I certainly can't make any sense of your "by the way, $N = 2n$" comment; is the $n$ at the top of the sum supposed to be little or big? – John Hughes Mar 16 '17 at 20:47
• Are you trying to compute the probability that the walker never returns to the origin in the first $N$ steps? Or that that they don't return to the origin at the $N^{\text{th}}$ step? These are different questions, and you cannot ignore $N$ odd in the former case. – Jason Mar 16 '17 at 20:47
• @Jason the question is the following: " Find the probability that an $N$-step one dimensional random walk (on a lattice) never returns to its origin, i.e to its starting point". I would appreciate it if you can answer both question that you posed here in your comment; if you know of a reference where these are discussed even better; thanks! – MathematicalPhysicist Mar 17 '17 at 5:43

You actually more or less have the answer to the question you asked, but let's go through it. Let $S_n=\sum_{k=1}^nX_k$ be a random walk started at the origin such that

$$p=P(X_k=1)=1-P(X_k=-1)=1-q$$

Let $\tau$ be the first return time. Observe that

$$P(\tau=2n\,|\,S_{2n}=0)=qP(A_n^+\,|\,S_{2n-1}=1)+pP(A_n^-\,|\,S_{2n-1}=-1)$$

where $A_n^+=\{S_k>0\text{ for }k=1,\ldots,2n-1\}$ and $A_n^-=\{S_k<0\text{ for }k=1,\ldots,2n-1\}$. By the Ballot theorem we have

$$P(A_n^+\,|\,S_{2n-1}=1)=P(A_n^-\,|\,S_{2n-1}=-1)=\frac1{2n-1},$$

so

$$P(\tau=2n\,|\,S_{2n}=0)=q\cdot\frac1{2n-1}+p\cdot\frac1{2n-1}=\frac1{2n-1}.$$

It follows that

$$P(\tau\le N)=\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}P(S_{2n}=0)=\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}{{2n}\choose n}(pq)^n$$

where the second equality is a simple counting argument. In particular, the probability that the walker does not return in the first $N$ steps is

$$P(\tau>N)=1-\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}{{2n}\choose n}(pq)^n$$

which is more or less what you wrote, modulo unnecessarily assuming $N$ was even. (Of course, the probability that the walker does not return on the $N^\text{th}$ step is $1-\frac1{N-1}{N\choose {N/2}}(pq)^{N/2}$ if $N$ is even and $1$ otherwise.) I doubt you're going to get a much more explicity result than this, however if you let $N\to\infty$ then we indeed recover the result you stated that

$$P(\tau<\infty)=1-|p-q|,$$

that is, that the probability that the walker never returns is $|p-q|$.

If the question is just for the N-th step, where N is even ($N=2k$), then it is simply $$1-C(N, k)p^kq^k$$

If the question is that is never returns within the first N step, then the Reflection Principle can be used to solve the problem.