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?


N.B $$N=2n$$

  • $\begingroup$ 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? $\endgroup$ – John Hughes Mar 16 '17 at 20:27
  • $\begingroup$ Is it correct? I am not sure. $\endgroup$ – MathematicalPhysicist Mar 16 '17 at 20:28
  • $\begingroup$ 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? $\endgroup$ – John Hughes Mar 16 '17 at 20:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Jason Mar 16 '17 at 20:47
  • $\begingroup$ @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! $\endgroup$ – 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


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


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




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


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.


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.