El caballo vuelve a la esquina en el tablero de ajedrez -- número medio de pasos

Question

Contexto: Mi amigo me planteó un problema en el desayuno hace algún tiempo. Se supone que tiene una solución fácil y con truco. No puedo resolverlo.

El problema: Supongamos que hay un caballo en una esquina determinada (0,0) de un tablero de ajedrez de 8x8. El caballo se mueve según las reglas habituales (2 en una dirección, 1 en la ortogonal) y sólo se permiten movimientos legales (no se puede hacer un túnel en la pared, etc.). El caballo se mueve al azar (es decir, en una posición determinada, genera un conjunto de todas las nuevas posiciones posibles y legales, y elige una al azar). ¿Cuál es el número medio de pasos tras los cuales el caballo vuelve a su esquina inicial?

En resumen: Un caballero comienza en (0,0). Cuántos pasos de media tarda en volver a (0,0) a través de un paseo aleatorio (pero sólo movimientos legales del caballo).

Mi intento: (descargo de responsabilidad: no sé mucho sobre cadenas de Markov).

El problema es una cadena de Markov. Hay $8\times8 = 64$ posibles estados. Existen probabilidades de transición entre los estados que son fáciles de generar. He generado una $64 \times 64$ matriz de transición $M_{ij}$ utilizando un simple trozo de código, ya que parecía demasiado grande para hacerlo a mano.

La posición inicial es $v_i = (1,0,0,...) = \delta_{0i}$ .

La probabilidad de que el caballo esté en la esquina (estado 0) después de $n$ pasos es $$ P_{there}(n) = (M^n)_{0j} v_j \, . $$ También necesito encontrar la probabilidad de que el caballero no haya alcanzado el estado 0 en ninguna de las anteriores $n-1$ pasos. La probabilidad de que el caballo no esté en la esquina después de $m$ pasos es $1-P_{there}(m)$ .

Por lo tanto, la probabilidad total de que el caballo esté en la esquina por primera vez (sin tener en cuenta la salida) después de $n$ pasos es $$ P(n) = \left ( \prod_{m=1}^{n-1} \left [ 1 - \sum_{j = 0}^{63} (M^m)_{0j} v_j \right ] \right ) \left ( \sum_{j = 0}^{63} (M^n)_{0j} v_j \right ) $$ Para calcular el número medio de pasos para volver, evalúo $$ \left < n \right >= \sum_{n = 1}^{\infty} n P(n) \, . $$ Mi problema: El enfoque que he descrito debería funcionar. Sin embargo, tuve que utilizar un ordenador debido al tamaño de las matrices. Además, el $\left < n \right >$ parece converger con bastante lentitud. Tengo $\left < n \right > \approx 130.3$ numéricamente y mi amigo afirma que está mal. Además, mi solución no es nada sencilla. ¿Podría echarle un vistazo?

¡Muchas gracias! -SSF

Answer 1

Detalles del método mencionado en el comentario de @Batman:

Podemos ver cada casilla del tablero de ajedrez como un vértice de un gráfico formado por $64$ vértices, y dos vértices están conectados por una arista si y sólo si un caballo puede moverse de una casilla a otra mediante un único movimiento legal.

Como el caballo puede moverse a cualquier otra casilla partiendo de una casilla aleatoria, el grafo está conectado (es decir, cada par de vértices está conectado por un camino).

Ahora, dado un vértice $i$ del gráfico, dejemos que $d_i$ denotan el grado del vértice, que es el número de aristas conectadas al vértice. Esto equivale al número de movimientos posibles que un caballo puede hacer en ese vértice (casilla del tablero de ajedrez). Como el caballo se mueve al azar, las probabilidades de transición de $i$ a sus vecinos es $1/d_i$ .

Ahora bien, como la cadena es irreducible (ya que el gráfico es conexo) la distribución estacionaria de la cadena es única. Llamemos a esta distribución $\pi$ . Ahora afirmamos lo siguiente:

Reclamación Dejemos que $\pi_j$ denotan $j^\text{th}$ componente de $\pi$ . Entonces $\pi_j$ es proporcional a $d_j$ .

Prueba Dejemos que $I$ sea la función sobre los vértices del grafo tal que $I(i)=1$ si $i$ es vecino de $j$ y $I(i)=0$ de lo contrario. Entonces

$$ d_j=\sum_i I(i)=\sum_i d_i \cdot \frac{I(i)}{d_i} = \sum_i d_i p_{ij} $$ donde $p_{ij}$ es la probabilidad de transición de $i$ a $j$ . Por lo tanto, tenemos $dP=d$ donde $P$ es la matriz de transición de la cadena, y $d=(d_1,\cdots,d_j,\cdots,d_{64})$ . Así, $\pi P=\pi \implies$ Reclamación

Por lo tanto, se deduce que después de normalizar tenemos

$$ \pi_j=d_j/\sum_i d_i $$

Por último, recordamos el siguiente teorema

Teorema Si la cadena es irreducible y recurrente positiva, entonces

$$ m_i=1/\pi_i $$ Donde $m_i$ es el tiempo medio de retorno del estado $i$ y $\pi$ es la única distribución estacionaria.

Así, si llamamos al vértice de la esquina $1$ tenemos

$$ m_1=1/\pi_1 $$

Puede comprobar que $\sum_i d_i = 336$ y tenemos $d_1=2$ (en la esquina el caballero puede hacer como máximo $2$ movimientos legales. Por lo tanto, $\pi_1=1/168$ y

$$ m_1=168 $$

Answer 2

Lo primero que hacemos es encontrar una distribución estable para el proceso de Markov. Vemos que el proceso será estable si la masa de cada casilla del tablero de ajedrez es proporcional al número de movimientos del caballo que se alejan de ella; entonces el proceso moverá una masa de 1 a lo largo de cada movimiento posible del caballo, por lo que cada casilla con n movimientos desde ella tendrá una masa de n entrando y una masa de n saliendo, de modo que todo se equilibra.

A continuación, queremos encontrar la masa total del sistema. Este es el número total de movimientos posibles del caballo; hay 8 direcciones posibles en las que un caballo puede moverse, y cada dirección puede empezar desde una casilla de 6x7, así que habrá 8*6*7 = 336 movimientos posibles, y esa es la masa total de la distribución.

Como un cuadrado de esquina tiene una masa de 2, eso representa 2/336 = 1/168 de la masa de la distribución. Como tenemos un proceso recurrente conectado, un paseo aleatorio infinito desde cualquier casilla estará en esa esquina concreta 1/168 de las veces. Eso significa que el tiempo medio entre visitas a la esquina será de 168.