Probabilidad de que la caminata aleatoria alcance el estado kkk por primera vez en el paso nnn

Después de algunas investigaciones, parece ser el caso de que hay

$$f(k,\ell)=\frac{k+1}{k+1+\ell}{k+2\ell\choose\ell}$$ caminos al estado$k\geq0$en$k+2\ell$pasos que nunca superan el$k$'th estado. Esto es equivalente a la cantidad de formas de moverse al estado$k+1$por primera vez despues$k+1+2\ell$pasos. Por sustitución y probabilidad simple, obtenemos un $$\frac{k}{k+\ell}{k-1+2\ell\choose\ell}p^{k+\ell}q^{\ell}$$ probabilidad de alcanzar el estado$k$por primera vez despues$k+2\ell$pasos.

Podemos probar nuestra fórmula para$f$por inducción Para$\ell=0$la respuesta es obviamente$1$, que coincide con la fórmula dada. Para$k=-1$la respuesta es obviamente$0$, que también coincide con la fórmula dada. Para$\ell>0$y$k\geq0$tenemos dos opciones para el primer movimiento: derecha o izquierda. Si vamos a la izquierda, hay$f(k+1,\ell-1)$opciones, y si vamos a la derecha hay$f(k-1,\ell)$opciones Por lo tanto, en total tenemos

$$\begin{align} f(k+1,\ell-1)+f(k-1,\ell) &=\frac{k+2}{k+2+\ell-1}{k+1+2(\ell-1)\choose\ell-1}+\frac{k}{k+\ell}{k-1+2\ell\choose\ell} \\&=\frac{(k+2)(k+2\ell-1)!}{(k+\ell+1)(\ell-1)!(k+\ell)!}+\frac{k(k+2\ell-1)!}{(k+\ell)\ell!(k+\ell-1)!} \\&=\frac{(k+2)(k+2\ell-1)!}{(\ell-1)!(k+\ell+1)!}+\frac{k(k+2\ell-1)!}{\ell!(k+\ell)!} \\&=\frac{\ell(k+2)(k+2\ell-1)!}{\ell!(k+\ell+1)!}+\frac{(k+\ell+1)k(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(\ell(k+2)+(k+\ell+1)k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell k+2\ell+k^2+k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell+k)(k+1)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(k+1)(k+2\ell)!}{\ell!(k+\ell+1)!} \\&=f(k,\ell) \end{align}$$ opciones Por principio de inducción, esto prueba la corrección de la fórmula para$f$.

Es cierto que, aunque esto resuelve el problema, no es una buena solución. Encontré la fórmula simplemente experimentando durante media hora, y la prueba es muy algebraica y no muy agradable de ver. Si a alguien se le ocurre una prueba combinatoria, ¡sería mucho mejor! Sin duda voy a pensar en ello ahora.

Una función generadora

Sea el número de formas de llegar a la posición$s$por primera vez en el paso$n$ser$a_{s,n}$. El número de caminatas unilaterales de longitud$2k$es$\frac1{k+1}\binom{2k}{k}$, con función generadora$\frac{1-\sqrt{1-4x}}{2x}$. Para llegar primero a la posición$s$en paso$n$, podemos contar el número de formas de llegar primero a la posición$s-1$en$n-2k-1$pasos por el número de caminatas unilaterales de longitud$2k$y suma para todos$k$. Eso es,

$$a_{s,n}=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}\,a_{s-1,n-2k-1}\tag1$$ Si establecemos la función generadora $$f_s(x)=\sum_{n=0}^\infty a_{s,n}x^n\tag2$$ entonces, usando$\frac{1-\sqrt{1-4x^2}}{2x}=\sum\limits_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^{2k+1}$, la fórmula del producto de Cauchy y$(1)$implicar $$f_s(x)=f_{s-1}(x)\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)\tag3$$ y desde$f_0(x)=1$, rendimientos de inducción $$\bbox[5px,border:2px solid #C0A000]{f_s(x)=\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^{\large s}}\tag4$$ Por lo tanto, si la probabilidad de un '$+1$'paso es$p$y de un '$-1$'paso es$1-p$, entonces la probabilidad de$\frac{n+s}2$'$+1$'pasos y$\frac{n-s}2$'$-1$'pasos es$a_{s,n}p^{\frac{n+s}2}(1-p)^{\frac{n-s}2}=\left(\frac{p}{1-p}\right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. resumiendo$n$da la probabilidad de llegar a la posición$s$en absoluto para ser $$\begin{align} \left(\frac{p}{1-p}\right)^{s/2}f_s\!\left(\sqrt{p(1-p)}\right) &=\left(\frac{1-|1-2p|}{2(1-p)}\right)^{\large s}\\[3pt] &=\left\{\begin{array}{}\left(\frac{p}{1-p}\right)^s&\text{if }p\lt\frac12\\1&\text{if }p\ge\frac12\end{array}\right.\tag5 \end{align}$$

---

Una forma cerrada

Para derivar una forma cerrada de$a_{s,n}$, primero consideramos la serie

$$\sum_{n=0}^\infty b_{s,n}x^n=\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{\large s}\tag6$$ donde, comparando$(4)$y$(6)$, obtenemos $$\begin{align} a_{s,s+2n}&=b_{s,n}\\ a_{s,s+2n+1}&=0 \end{align}\tag7$$ Usando el hecho de que $$\left(\frac{1-\sqrt{1-4x}}{2x}\right)^2=\frac1x\frac{1-\sqrt{1-4x}}{2x}-\frac1x\tag8$$ obtenemos la relacion $$b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}\tag9$$ Lo sabemos $$\begin{align} b_{0,n}&=[n=0]\\[3pt] b_{1,n}&=\frac1{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1} \end{align}\tag{10}$$ lo que implica que $$\begin{align} b_{2,n}&=\frac1{n+2}\binom{2n+2}{n+1}=\binom{2n+1}{n}-\binom{2n+1}{n-1}\tag{11}\\[6pt] b_{3,n}&=\frac1{n+3}\binom{2n+4}{n+2}-\frac1{n+2}\binom{2n+2}{n+1} =\binom{2n+2}{n}-\binom{2n+2}{n-1}\tag{12} \end{align}$$ Está apareciendo un patrón; eso es, $$\begin{align} b_{s,n} &=\binom{2n+s-1}{n}-\binom{2n+s-1}{n-1}\\[3pt] &=\frac{s}{2n+s}\binom{2n+s}{n}\tag{13} \end{align}$$ que satisface$(9)$utilizando la fórmula de Pascal . Por lo tanto, aplicando$(7)$rendimientos $$\bbox[5px,border:2px solid #C0A000]{a_{s,n}=\left\{\begin{array}{} \frac sn\binom{n}{(n-s)/2}=\binom{n-1}{(n-s)/2}-\binom{n-1}{(n-s-2)/2}&\text{if }2\mid n-s\\ 0&\text{if }2\nmid n-s \end{array}\right.}\tag{14}$$

Esta respuesta es una extensión de la de @SmileyCraft. Como dice en su respuesta, sería bueno tener una prueba combinatoria. Podría haber encontrado uno. El problema parece similar en espíritu al que tiene una cuadrícula cuadrada, comienza en la esquina inferior izquierda y necesita llegar a la esquina superior derecha y encontrar la cantidad de caminos donde no cruza la diagonal principal de la cuadrícula (está bien tocarlo). En ese caso, el número de dichos caminos son los números catalanes.

$$C_n = \frac{2n \choose n}{n+1} = {2n \choose n} - {2n \choose n-1}$$

Ahora, siguiendo el ejemplo de esto, la fórmula que @SmileyCraft tiene arriba también se puede escribir como:

$$f(k,l) = \frac{k+1}{k+1+l} {k+2l \choose l} = {k+2l \choose l} - {k+2l \choose l-1} \tag{1}$$

Ahora, el problema aquí es que la caminata aleatoria no cruza$k$se puede convertir en un problema de rejilla. Básicamente tenemos (según la convención de @SmileyCraft)$l$colas y$l+k$cabezas y es necesario colocarlas de tal manera que nunca crucen el$k$. Esto es completamente equivalente a decir que iremos a la derecha si sale cruz y subiremos si sale cara en una cuadrícula que tiene$l+k$filas y$l$columnas

Otra forma de ver esto es graficar en el eje x el número de lanzamiento y en el eje y la puntuación de la caminata aleatoria. Ahora, imagina cualquier camino que vaya desde$(0,0)$a$(k+2l,k)$. Ahora, simplemente gire la imagen completa 45 grados y obtendrá la cuadrícula.

Así que la fórmula para$f(k,l)$anterior es simplemente el número de formas de ir desde la parte inferior izquierda a la parte superior derecha de una cuadrícula con$l$filas y$l+k$columnas de tal manera que el camino nunca cruce la línea$y=x+k$.

Pero, ¿cómo demostramos que es equivalente a la ecuación (1) anterior? Hice trampa y usé el mismo razonamiento que la respuesta de @Marcus M aquí . Dice así:

Sabemos que las rutas totales en nuestra cuadrícula son$k+2l \choose l$. Los buenos caminos son los que nunca cruzan la línea$y=x+k$. Entonces,

# buenos caminos = # caminos - # malos caminos

Ahora, cualquier mal camino cruza la línea$y=x+k$. Entonces, debe tocar la línea.$y=x+k+1$(la diagonal justo encima).

Divida cualquier ruta de este tipo en dos partes. La porción desde el origen hasta cuando toca el$y=x+k+1$línea y la porción después de eso. La primera parte se puede reflexionar sobre el$y=x+k+1$. Y esto lleva a una biyección a un camino desde$(-(k+1),(k+1))$a$(l,k+l)$. Por lo tanto, los malos caminos se pueden asignar a caminos desde la parte inferior izquierda hasta la parte superior derecha de otra cuadrícula cuya altura es$(k+l)-(k+1)=l-1$. Pero no cambiamos la longitud total de la ruta, por lo que la longitud total de las rutas incorrectas sigue siendo$k+2l$. Por lo tanto, el número de malos caminos es$k+2l \choose l-1$.

Poniendo todo esto junto, obtenemos la ecuación (1) anterior. La siguiente imagen muestra esto para$k=3$y$t=2$.

Supongo que puedo resolver este problema de una manera menos combinatoria.

Para facilitar la comprensión, solo daré un bosquejo de la demostración.

Algunas abreviaturas:

• SRW = Paseo aleatorio simple
• [L/R]HS = [izquierda/derecha] lado de la mano
• iid = independientes e idénticamente distribuidos
• # = número

---

Primero necesito presentar el Principio de reflexión para SRW .

Considere SRW:$S_n=X_1 + \cdots + X_n$y$S_0=0$.$\{X_i\}_{i=1}^{n}$son variables aleatorias iid.

Denotar$M_n$es la posición más lejana que podemos alcanzar en$n$pasos (más formalmente,$M_n=\max_{i\in[0,n]} S_i$). Entonces

$$\#(M_n\geqslant x, S_n=y) = \#(S_n=2x-y), \quad \text{if}~~x\geqslant y \tag{Reflection Principle}$$

Esto es intuitivo:

1. $x$es visitado antes o en$n$(existe$t\leqslant n$, tal que$S_t=x$);
2. Para cada ruta en LHS, puede "reflejar" o "voltear" todos los comportamientos después$t$para obtener una ruta en RHS, y viceversa.

---

Entonces podemos resolver fácilmente este problema.

Como solo es posible cuando$n$y$k$tienen la misma rareza, y$n\geqslant k$, podemos denotar$n=k+2l$.

$$\begin{split} & \#(\text{first visit $k$ at $n$th step}) \\ =& \#(M_{n-1}\leqslant k-1, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(M_{n-1}\geqslant k, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(S_{n-1}=k+1) \\ =& \binom{n-1}{k+l-1} - \binom{n-1}{k+l} \\ \end{split}$$

---

Podemos usar 2 casos simples para probar este resultado:

1. $\#=1$cuando$n=k$o$l=0$: $$\binom{k-1}{k-1} - \binom{k-1}{k} = 1 - 0 = 1$$
2. $\#=k$cuando$n=k+2$o$l=1$: $$\binom{k+1}{k} - \binom{k+1}{k+1} = (k+1) - 1 = k$$