Me voy a centrar la atención en algunos detalles de su ejemplo, pero los argumentos que llevan a más grandes ejemplos.
Como se vio, hay 25 células en el interior de una de 3 pasos de la radio de origen:
.
. . .
. . . . .
. . . o . . .
. . . . .
. . .
.
La primera cosa a hacer es reconocer que la simetría de las consideraciones de reducir el cálculo final de las células cuyo centro se encuentran dentro de un ángulo para el origen de $[0,\pi/4]$:
. ⁄
. . . ⁄
. . . + +
. . . + + + + ------
. . . . .
. . .
.
De que los recortes de 25 células que se encuentran dentro de una 3-el paso del radio de 6. En grandes problemas se reducen a poco más de 1/8 de la total.
La segunda cosa que veo es que la paridad consideraciones reducir cálculo aún más, la eliminación de 3 de los 6 celdas (por ejemplo, si usted se mueve en tres pasos, usted no puede terminar de vuelta en donde empezar). Tan sólo tendrá que trabajar tres células:
.
. . .
. . . . c
. . . . a . b
. . . . .
. . .
.
Este paso será reducir el cálculo por alrededor de la mitad.
Todas las otras células que no tienen probabilidad cero después de 3 pasos será igual a uno de los
tres células marcadas.
Ahora reconocen que si se toman los tres células, y añadir otra celda:
.
. . c'
. . . . c
. . . . a . b
. . . . .
. . .
.
a continuación, por rotación, que cubren todo el positivo de la probabilidad de las células con el derecho de la probabilidad. Por lo tanto, si $n(.)$ es el número de maneras de llegar a la celda $i$, $n(a)+n(b)+2n(c)=64/4=16$, y para las probabilidades, si $p_3(i)$ es la probabilidad de llegar a la posición $i$ a paso $3$, $p_3(a)+p_3(b)+2p_3(c)=1/4$. Esto proporciona una forma útil de verificar que no falte a ninguna de probabilidad.
(En general, sería el doble de cualquier célula que no en el eje x o en una exacta diagonal en
este cálculo. Y en los pasos numerados, el origen se cuenta sólo una vez, por supuesto).
Así que si usted tiene un método sistemático para la obtención de dichos recuentos de células/probabilidades, usted sólo tiene que hacer.
Sin embargo, como para la elaboración de las probabilidades, tiendo a buscar a hacerlo de forma recursiva, un paso a la vez, esencialmente convolving el solo paso probabilidades como un núcleo con el resultado del paso anterior.
Paso 0. Empezamos con todas las de la probabilidad en el centro:
· · ·
· · · · ·
· · 1 · ·
· · · · ·
· · ·
Paso 1. Considerar la primera, de un solo paso
· · · · · · · 1/4 · ·
↑
· · ← 1 → · · ===> · 1/4 0 1/4 ·
↓
· · · · · · · 1/4 · ·
Este paso único resultado que ahora puede ser tratada tratada como un núcleo en el futuro, cualquier paso, tomamos las probabilidades en cualquier lugar dado en el paso anterior, de convolución con este bivariante kernel y para obtener el siguiente paso. En la práctica esto significa que usted tome una cantidad dada de probabilidad, se divide por 4 y agregarlo a la celda probabilidades de un paso en cada una de las 4 direcciones, recorrer todas las celdas (en realidad los grandes problemas que miraba a enfoques más eficientes, pero esto va a hacer por el problema actual). Si lo haces a través de todas las células, que ha calculado todas las probabilidades en un paso en términos de la anterior.
Pero, útil, podemos cambiar esta situación. Para calcular la probabilidad de una determinada celda, el promedio de los 4 probabilidades del paso anterior que fueron un paso en cada una de las 4 direcciones a su alrededor:
$p_{i,j}(t)=\frac{1}{4}[p_{i-1,j}(t-1)+p_{i,j-1}(t-1)+p_{i+1,j}(t-1)+p_{i,j+1}(t-1)]$
Podemos emplear el mencionado anteriormente simetrías, así que sólo tenemos que seguir la pista de las células dentro de los 1/8 de arco (incluyendo su límite).
Revisado el Paso 1:
· ·
· · ·
· · · ·
o q · · ·
Donde $p_1(o)=0$ $p_1(q)=\frac{1}{4}$ (yo usé $q$ a de "el barrio").
Y revisado el Paso 2:
· ·
· · ·
w · · ·
o . x · ·
El punto marcado $w$ recibe 1/4 de la probabilidad de cada lado de la misma. Pero solo 2 de esas células no son cero:
0
↓
q → w ← 0
↑
q
por lo $p_2(w) = 2(1/4)^2 = 1/8$
Mientras tanto, $x$ es sólo para llamar la probabilidad de su izquierda, por lo $p_2(x) = (1/4)^2 = 1/16$
Sin embargo, también hay un punto de $o$, que puede heredar la probabilidad de cualquier lado, por lo $p_2(o)=4(1/4)^2=1/4$.
Verificación: $p_2(o)+4(p_2(w)+p_2(x))=1/4 + 4/8 + 4/16 = 1$
Usted puede continuar de esa manera a
una revisión Paso 3:
· · · ·
· · · · · ·
w · · · ===> . c · ·
o . x · · . a . b ·
$p_3(a) = [p_2(o)+2p_2(w)+p_2(x)]/4 = [\frac{1}{4} + 2\frac{1}{8} + \frac{1}{16}]/4 =9/64$
$p_3(b) = p_2(x)/4 = (\frac{1}{16})/4 = 1/64$
$p_3(c) = [p_2(w)+p_2(x)]/4 = [\frac{1}{8} + \frac{1}{16}]/4 =3/64$
Verificación: $p_3(a)+p_3(b)+2p_3(c)=[9+1+2\times 3]/64=1/4$.
Y así sucesivamente para el paso 4, 5, etc.
Paso 4 iría como:
· · · ·
· · · · · ·
· c · · ===> w · y ·
· a · b · o · x · z
Esto es fácil escribir código para recorrer.
