Recuento combinatorio de paseos aleatorios simples no negativos

Question

Dado un paseo aleatorio simple $S_n = \sum_{i=0}^n X_i$ donde $X_0=0$ y $X_{i>0} \in \{-1,1\}$ el recuento de positivo paseos (para los que $\forall i>0 : S_i > 0 $ ) que terminan en $u > 0$ (es decir $S_n = u$ ) viene dada por: \begin{equation} \pi_n = {n \choose {} \frac{n+u}{2}} - {n \choose \frac{n+u}{2}+1} . \end{equation}

¿Existe una expresión combinatoria similar para no negativo paseos (para los que $\forall i >0 : S_i \geq 0$ ) que terminan en $u\geq0$ ?

Gracias.

Answer 1

Si "eliminas" el primer paso puedes transformar un paseo positivo en uno no negativo.

Sea $\mathbf s:=(s_0,\ldots,s_n)$ sea un paseo no negativo con $n$ pasos. A continuación, $\mathbf s':=(0,s_0+1,\ldots,s_n+1)$ es un paseo positivo con $n+1$ pasos. Por el contrario, si $\mathbf s':=(s'_0,\ldots,s'_{n+1})$ es un paseo positivo con $n+1$ pasos, entonces $\mathbf s:=(s'_1-1,\ldots,s'_{n+1}-1)$ es un paseo no negativo con $n$ pasos. Esto da una biyección $\mathbf s\mapsto\mathbf s'$ entre paseos no negativos con $n$ pasos y paseos positivos con $n+1$ pasos. Por tanto, el número de paseos no negativos con $n$ pasos es sólo $\pi_{n+1}$ .