Paseo aleatorio: reyes en un tablero de ajedrez

Tengo una pregunta sobre la caminata aleatoria de dos reyes en un tablero de ajedrez 3 × 3.

Cada rey se mueve al azar con la misma probabilidad en este tablero de ajedrez: vertical, horizontal y diagonal. Los dos reyes se mueven independientemente uno del otro en el mismo tablero de ajedrez. Ambos comienzan en el mismo cuadrado y luego se mueven independientemente.

¿Cómo podríamos encontrar la probabilidad en el tiempo ambos están en el mismo cuadrado, ya que va al infinito?$n$$n$

Aprovechemos la simetría para simplificar los cálculos.

El tablero de ajedrez y sus movimientos permanecen iguales cuando el tablero se refleja verticalmente, horizontalmente o diagonalmente. Esto descompone sus nueve cuadrados en tres tipos, sus órbitas bajo este grupo de simetría. En consecuencia, cada rey puede estar en uno de tres "estados": un cuadrado de esquina ($C$), un cuadrado de borde ($E$), o el cuadrado central ("medio") ($M$) (Un estado ignora en qué cuadrado en particular se encuentra un rey y rastrea solo su clase de equivalencia bajo el grupo de simetrías).

Los siguientes resultados son inmediatos:

• Desde un cuadrado de esquina, hay dos transiciones a cuadrados de borde y una transición a un cuadrado del medio. Debido a que las tres transiciones son equiprobables,

  $$\Pr(C \to E) = 2/3,\quad \Pr(C \to M) = 1/3.$$

  Esto proporciona una fila en una matriz de transición para los estados .$(0, 2/3, 1/3)$$(C, E, M)$

• Desde un cuadrado de borde hay dos transiciones a cuadrados de esquina, dos a otros cuadrados de borde y uno al cuadrado del medio. Esto da una segunda fila en una matriz de transición.$(2/5, 2/5, 1/5)$

• Desde el cuadrado del medio hay cuatro transiciones a cuadrados de esquina y cuatro a cuadrados medios. La tercera fila de una matriz de transición, por lo tanto, es .$(4/8, 4/8, 0) = (1/2, 1/2, 0)$

En este gráfico que representa esta cadena de Markov, las probabilidades de transición se representan tanto por el grosor del borde como por el color:

Por inspección o de otra manera, encontramos que un vector propio izquierdo de su matriz de transición

is . Esta afirmación se verifica fácilmente realizando la multiplicación: El valor propio manifiestamente es . Debido a que todos los estados están conectados, da las probabilidades limitantes de que cada rey esté en cada estado; solo necesitamos reescalar sus componentes para sumar la unidad:$\omega = (3, 5, 2)^\prime$$\omega \mathbb{P} = 1 \omega.$$1$$\omega$

(Aquí es donde cosechamos los beneficios de explotar la simetría: en lugar de trabajar con una matriz de nueve por nueve de elementos, solo tenemos que calcular con una matriz de por tres de tres elementos. La reducción del problema de nueve estados a tres pagado cuadráticamente al reducir el esfuerzo computacional por un factor de )$81$$9$$(9/3)^2 = 9$

El (limitante) posibilidad de que ambos reyes están en un estado de probabilidad (limitante) es decir porque los reyes se mueven independientemente. La posibilidad de que ambos reyes estén en la misma celda se encuentra condicionando el estado: por simetría, cada celda en un estado dado tiene la misma probabilidad limitante, por lo que si ambos reyes se encuentran en un estado tienen celdas , la probabilidad de que ambos están en la misma celda es . De donde la solución es$s$$\omega_s$$\omega_s^2$$s$$k_s$$1/k_s$

Como los dos reyes se mueven independientemente, puedes considerarlos por separado. Si el tablero es de tamaño finito y no tiene subsecciones cerradas, este es uno de esos casos en los que se puede encontrar la distribución estacionaria resolviendo la ecuación de equilibrio detallada.

En este caso, a medida que va al infinito, la probabilidad de que un rey esté en un cuadrado se vuelve proporcional al número de cuadrados adyacentes, es decir, tres para cada cuadrado de esquina, cinco para cada cuadrado de borde y ocho para el cuadrado central. Esto equivale a , por lo que la posibilidad de estar en el cuadrado del medio es , en cualquier cuadrado de la esquina es , y en cualquier cuadrado del borde es .$n$$40$$8/40$$3/40$$5/40$

Como esto es cierto para ambos reyes independientemente, la posibilidad de que ambos estén en el cuadrado del medio es , de que ambos estén en cualquier cuadrado de la esquina es , y en cualquier borde cuadrado es . Entonces, la posibilidad de que estén en el mismo cuadrado se aproxima a medida que acerca al infinito.$(8/40)^2 = 64/1600$$(3/40)^2=9/1600$$(5/40)^2=25/1600$$\frac{64+4\times9+4\times25}{1600} = \frac{200}{1600} = \frac{1}{8}$$n$

Puedes resolverlo usando la matriz de probabilidad de transición.

$\begin{bmatrix} C_1 & C_2 & C_3 \\ C_4 & C_5 & C_6 \\ C_7 & C_8 & C_9 \\\end{bmatrix}$

Construya la matriz de probabilidad de transición, usando la probabilidad de una celda a otra. Por ejemplo: . P será una matriz de .$P[C_1, C_2] = P[C_1, C_4]= P[C_1, C_5] = \frac{1}{3}$$9 \times 9$

Ahora puede calcular las probabilidades estacionarias (ya que todos los estados son recurrentes).

Resuelva modo que .$\pi P = \pi$$\sum \pi =1$

Esto da la probabilidad de un rey en un cuadrado particular como n grande. Use la propiedad de independencia para llegar a la probabilidad requerida.