23 votos

Caballero de regresar a la esquina en un tablero de ajedrez-el número medio de pasos

Contexto: Mi amigo me dio un problema en el desayuno hace algún tiempo. Se supone que tiene un fácil truco-con la participación de solución. No lo puedo entender.

Problema: Vamos hay que ser un caballero (caballo) en una esquina particular (0,0) en un tablero de ajedrez de 8x8. El caballero se mueve de acuerdo a las reglas habituales (2 en una dirección, 1 ortogonal en la uno) y sólo los movimientos legales son autorizados (no de la pared de túneles, etc). El caballero se mueve al azar (es decir, a una posición en particular, genera un conjunto de todos los posibles y legales de las nuevas posiciones, y elige uno al azar). ¿Cuál es el número promedio de pasos después de que el caballero vuelve a su rincón de partida?

Para resumir: Un caballero que se inicia en (0,0). Cuántos pasos en promedio se tarda en volver a (0,0) a través de un azar (pero sólo legal caballero se mueve) a pie.

Mi intento: (descargo de responsabilidad: yo no sé mucho acerca de las cadenas de Markov.)

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

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

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

Por lo tanto, el total de la probabilidad de que el caballero está en la esquina de la primera vez (sin tomar en cuenta el inicio) 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 promedio de pasos para volver, me evaluar $$ \left < n \right >= \sum_{n = 1}^{\infty} n P(n) \, . $$ Mi problema: El enfoque que he descrito debe trabajar. Sin embargo, he tenido que utilizar un ordenador, debido a que el tamaño de las matrices. También, el $\left < n \right >$ parece convergen muy lentamente. Llegué $\left < n \right > \approx 130.3$ numéricamente y mi amigo dice que es incorrecto. Además, mi solución está lejos de ser simple. Por favor, eche un vistazo a esto?

Muchas gracias! -SSF

23voto

user160738 Puntos 1381

Los detalles del método mencionado en @Batman comentario:

Podemos ver cada cuadrado del tablero de ajedrez como un vértice en un grafo consta de $64$ vértices, y dos vértices están conectados por una arista si y sólo si el caballo puede moverse de una plaza a otra por un solo movimiento legal.

Desde el caballo puede mover a cualquier otro cuadrados a partir de un azar de la plaza, a continuación, el gráfico está conectado (es decir, cada par de vértices está conectado por un camino).

Ahora, dado un vértice $i$ de la gráfica, vamos a $d_i$ denotar el grado del vértice, que es el número de aristas conectadas con el vértice. Esto es equivalente al número de movimientos posibles que un caballero puede hacer en ese vértice (plaza de tablero de ajedrez). Desde que el caballero se mueve al azar, las probabilidades de transición de $i$ a sus vecinos,$1/d_i$.

Ahora desde que la cadena es irreducible (ya que el gráfico está conectado) la distribución estacionaria de la cadena es el único. Vamos a llamar a esta distribución $\pi$. Ahora le reclamo las siguientes:

Reclamación Deje $\pi_j$ denotar $j^\text{th}$ componente de $\pi$. A continuación, $\pi_j$ es proporcional a $d_j$.

La prueba Deje $I$ ser la función en los vértices del grafo tal que $I(i)=1$ si $i$ es un vecino de $j$, e $I(i)=0$ 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$$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})$. Por Lo Tanto $\pi P=\pi \implies$ Demanda

Por lo tanto, se deduce que después de la normalización de la que hemos

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

Finalmente recordamos el siguiente teorema

Teorema Si la cadena es irreducible y positivo recurrente, a continuación,

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

Por lo tanto, si llamamos a la esquina vértice $1$, tenemos

$$ m_1=1/\pi_1 $$

Se puede comprobar que $\sum_i d_i = 336$, y tenemos $d_1=2$ (en la esquina caballero puede hacer en la mayoría de las $2$ movimientos legales. Por lo tanto, $\pi_1=1/168$ y

$$ m_1=168 $$

6voto

Deedlit Puntos 2238

Lo primero que tenemos que hacer es encontrar una distribución estable para el proceso de Markov. Vemos que el proceso será estable si la masa de cada cuadrado del tablero de ajedrez es proporcional al número de caballero se mueve llevando fuera de él; a continuación, el proceso de mover una masa de 1 a lo largo de cada una de las posibles caballero de moverse, por lo que cada cuadrado con n se mueve de que tendrá una masa de n moviendo en y una masa de n hacia fuera, así que todo lo equilibra.

A continuación, queremos encontrar la masa total del sistema. Este es el número total de posibles caballero se mueve; hay 8 posibles direcciones que un caballero puede mover, y cada dirección puede comenzar a partir de un 6x7 cuadrados, por lo que habrá 8*6*7 = 336 movimientos posibles, y que es la masa total de la distribución.

Desde una esquina de la plaza tiene una masa de 2, que representa 2/336 = 1/168 de la masa de la distribución. Ya tenemos la conexión de un proceso recurrente, un infinito de paseo aleatorio de cualquier cuadrado será en ese rincón particular 1/168 de la época. Eso significa que el promedio de tiempo entre las visitas a la esquina será 168.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X