Combinatorical Counting of Non-negative Simple Random Walks

Question

Given a simple random walk $S_n = \sum_{i=0}^n X_i$, where $X_0=0$ and $X_{i>0} \in \{-1,1\}$, the count of positive walks (for which $\forall i>0 : S_i > 0 $) that end in $u > 0$ (i.e. $S_n = u$) is given by: \begin{equation} \pi_n = {n \choose {} \frac{n+u}{2}} - {n \choose \frac{n+u}{2}+1} . \end{equation}

Is there a similar combinatorical expression for non-negative walks (for which $\forall i >0 : S_i \geq 0$) that end in $u\geq0$?

Thanks!

Answer 1

If you “remove” the first step you can transform a positive walk into a nonnegative one.

Let $\mathbf s:=(s_0,\ldots,s_n)$ be a nonnegative walk with $n$ steps. Then $\mathbf s':=(0,s_0+1,\ldots,s_n+1)$ is a positive walk with $n+1$ steps. Conversely, if $\mathbf s':=(s'_0,\ldots,s'_{n+1})$ is a positive walk with $n+1$ steps, then $\mathbf s:=(s'_1-1,\ldots,s'_{n+1}-1)$ is a nonnegative walk with $n$ steps. This gives a bijection $\mathbf s\mapsto\mathbf s'$ between nonnegative walks with $n$ steps and positive walks with $n+1$ steps. So the number of nonnegative walks with $n$ steps is just $\pi_{n+1}$.