On the number line, starting from 0. There is a probability of $p$ of moving 1 unit to the positive direction, and $1-p$ of moving 1 unit to the negative direction.

What is the probability the walk never reaches $-1$ after $n$ steps?


Let $P_n$ be the probability that the walk has still not visited $-1$ after $n$ steps. If $n$ is even, we can't be at $-1$, so $P_{n} = P_{n-1}$ for even $n$. Assume from now on that $n = 2m+1$ is odd.

For $0 \le r \le m$, let $P_{n,r}$ denote the probability that after $n=2m+1$ steps, the walk is at position $2r+1$ and has still not visited $-1$. We can count the number $N_{n,r}$ of such walks, as follows:

$N_{n,r} = T_{n,r} - V_{n,r}$

where $T_{n,r}$ is the total number of walks ending at $2r+1$ (including those that visit $-1$), and $V_{n,r}$ is the number of walks ending at $2r+1$ that do visit $-1$ on the way. A walk that ends at $2r+1$ consists of $m+r+1$ positive steps and $m-r$ negative steps, so $T_{n,r} = \binom{n}{m-r}$. To evaluate $V_{n,r}$, we need the following observation:

There is a 1-1 correspondence between walks ending at $2r+1$ that visit $-1$ on the way, and walks ending at $-(2r+3)$.

For, given a walk ending at $2r+1$ that visits $-1$, we can reflect the portion of it that occurs after its first visit to $-1$, to obtain a walk that ends at $-(2r+3)$. And vice versa.

A walk that ends at $-(2r+3)$ consists of $m-r-1$ positive steps and $m+r+2$ negative steps, so $V_{n,r} = \binom{n}{m-r-1}$, giving $N_{n,r} = \binom{n}{m-r} - \binom{n}{m-r-1}$. (If $r = m$, then we understand the second binomial term as zero.) Thus:

$P_{n,r} = p^{m+r+1}q^{m-r}\left(\binom{n}{m-r} - \binom{n}{m-r-1}\right)$

where $q = 1-p$. So the total probability of not visiting $-1$ in $n$ steps is

$P_n = \sum_{r=0}^m P_{n,r}$

This is a modification of the binomial distribution. I don't think it can be simplified any further, unless you want to use regularised incomplete beta functions.

  • $\begingroup$ Some $P_{n,r}$ is larger than 1. For example, $P_{1,0}=1/p$. How should that be handled? $\endgroup$ – Chao Xu Jan 18 '11 at 22:16
  • $\begingroup$ @Chao Xu: Sorry, misprint. I think it's correct now. $\endgroup$ – TonyK Jan 19 '11 at 7:16
  • $\begingroup$ Furthermore, every $P_n$ is a nondecreasing function of $p$. For a given $p$, the sequence $(P_n)$ is nonincreasing and converging to $0$ if $p\le\frac12$ and to $1-(q/p)$ if $p>\frac12$. $\endgroup$ – Did Jan 24 '11 at 14:08

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.