En una cuadrícula bidimensional infinita, definimos cuatro direcciones: norte, sur, este y oeste. Así pues, tenemos $4^n$ paseos aleatorios de longitud $n$ . Si terminamos donde empezamos, por cada paso al norte tenemos uno al sur, y de forma similar para el este y el oeste. Suponiendo que $k$ norte-sur y $n/2 -k$ pasos este-oeste, encontramos que el número de paseos posibles es $$\sum_{k=0}^{n/2}\frac{n!}{k!^2(n/2-k!)!^2}={n\choose n/2}\sum_{k=0}^{n/2}{n/2\choose k}^2={n\choose n/2}^2$$ un bello resultado que insinúa una interpretación más limpia. ¿Cómo podemos ver esto directamente desde la red?
Respuestas
¿Demasiados anuncios?
Desde $n$ debe ser uniforme para que el paseo se cierre, escribiré $n=2m$ . Sea $n_N,n_S,n_E$ y $n_W$ sea el número de pasos hacia el norte, el sur, el este y el oeste, respectivamente. Entonces $n_N=n_S$ y $n_E=n_W$ Así que $n_N+n_E=n_S+n_W=m$ y $n_N+n_W=n_S+n_E=m$ .
Obsérvese también que si elegimos $n_N,n_S,n_E$ y $n_W$ para que $n_N+n_E=n_S+n_W=m$ y $n_N+n_W=n_S+n_E=m$ , entonces automáticamente $n_N=n_S$ y $n_E=n_W$ .
Ahora imagínate trazando un $n$ -paso a paso comenzando con una franja de $n$ cuadrados y etiquetando cada cuadrado como N, S, E o W para los pasos al norte, sur, fácil y oeste, respectivamente. Sin embargo, lo haremos de una manera ligeramente impar. Primero elige cualquier $m$ cuadrados y marcarlos $\nearrow$ . Estos serán los $m$ escalones que van al norte o al este. A continuación, elija cualquier $m$ cuadrados y marcarlos $\nwarrow$ Estos serán los $m$ pasos que van al norte o al oeste. Evidentemente, este procedimiento puede llevarse a cabo en $\binom{2m}m^2$ formas. Ahora recorre la tira y cambia las marcas según las siguientes reglas:
- un cuadrado marcado con ambos $\nearrow$ y $\nwarrow$ está marcada como N.
- un cuadrado marcado sólo con $\nearrow$ está marcada como E.
- un cuadrado marcado sólo con $\nwarrow$ está marcada como W.
- un cuadrado sin marcar está marcado con una S.
De la observación del segundo párrafo se desprende que hemos trazado un gráfico para un camino que vuelve al origen, y no es difícil ver que cada $n$ -La trayectoria de un paso que vuelve al origen tiene un gráfico que se puede producir de esta manera. Hay $\binom{2m}m^2$ gráficos producidos de esta manera, por lo que hay $\binom{2m}m^2$ $n$ -caminos de paso que vuelven al origen.
Daniel Serodio
Puntos
1328
Voy a dar una intuición de por qué esto debe sostenerse, mientras sigo pensando en una forma combinatoria de verlo.
Cambiando un poco la notación, consideremos el $1$ - $D$ que vuelven al origen en el momento $2n$ . Claramente, hay $2n\choose n$ tales paseos.
Tome dos copias independientes de $1$ paseos dimensionales $X_n, Y_n$ y crear el nuevo $2$ proceso dimensional $R_n=(X_n,Y_n)$ . La probabilidad de retorno de $R_n$ es ${2n\choose n}^2$ y se puede ver que al girar por $45$ grados y la reducción de la escala por un factor de $\sqrt{2}$ se obtiene el habitual SRW en $2$ - $D$ y esta escala de rotación no cambia las probabilidades.
En una dimensión superior, no está muy claro cómo se rotaría, por lo que este argumento no se puede aplicar.
