Probability of never reach -1 for a 1D random walk of n steps

Question

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?

Answer 1

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.