Espera que el número de vueltas de una torre para mover a la parte superior derecha de la esquina?

Question

Supongamos que la torre se inicia en la parte inferior izquierda del cuadrado de un estándar $8 \times 8$ tablero de ajedrez. La junta directiva no contiene otras piezas.

El grajo al azar hace legal de ajedrez se mueven con cada giro directa (vertical u horizontal). La torre no puede permanecer inmóvil durante un turno. ¿Cuál es el número esperado de movimientos para la torre de la tierra en la parte superior derecha de la mayoría de los cuadrados?

Entiendo que la torre tiene 14 movimientos posibles para cada turno. El problema parece encajar el concepto de las cadenas de Markov, como la distribución de probabilidad de cualquier movimiento no depende de la anterior. Sin embargo, no entiendo cómo el enfoque de este cálculo.

Answer 1

Etiqueta de la junta de la $\{1,2,\cdots,8\}\times\{1,2,\cdots,8\}$. Una clave de la observación es que el número de coordenadas de la posición de la torre con la que son iguales a $8$ realiza una cadena de Markov, y, obviamente, la parte superior derecha de la plaza es la única plaza en la junta tal que este número es $2$. Por lo tanto, uno se pregunta, para la media de golpear tiempo de $2$ por una cadena de Markov en $\{0,1,2\}$ a partir de $0$ con las probabilidades de transición de la siguiente manera:

• La transición de $0\to0$: probabilidad de $\frac67$
• La transición de $0\to1$: probabilidad de $\frac17$
• La transición de $1\to0$: probabilidad de $\frac12$
• La transición de $1\to1$: probabilidad de $\frac37$
• La transición de $1\to2$: probabilidad de $\frac1{14}$

Luego de la usal enfoque funciona: se considera la media de golpear tiempo $t_k$ a partir de estado$k$, $t_2=0$ y, acondicionado en el primer paso de la cadena de Markov, se obtiene $$t_0=1+\tfrac67\cdot t_0+\tfrac17\cdot t_1,\qquad t_1=1+\tfrac12\cdot t_0+\tfrac37\cdot t_1+\tfrac1{14}\cdot0,$$ hence the desired expected time is $$t_0=70.$$ Quizás sorprendentemente, partiendo de la plaza del G7 se tarda exactamente el número de pasos para llegar a la (aparente) vecino de la plaza H8 de partir de la (aparente) más alejado de la plaza A1.

Más en general, por una junta de tamaño $n\times n$, $$t_0=n^2+n-2.$$

Answer 2

Usted puede simplificar este problema un poco al notar que podemos clasificar de plazas en la junta como en uno de los tres conjuntos: Conjunto de $A$ es el conjunto de $49$ plazas que no están en la fila o de la columna de la casilla de destino; set $B$ es el conjunto de $14$ plazas que están en la fila o de la columna de la casilla de destino, pero no el objetivo de la plaza en sí; y establecer $C$ es el conjunto de la casilla de destino.

Si la torre (en la plaza) en $A$, tiene probabilidades de transición de $P(A\to A)=\frac{12}{14}=\frac{6}{7}$, e $P(A\to B)=\frac{2}{14}=\frac17$. Si la torre está configurado $B$, las probabilidades de transición son $P(B\to A)=\frac12$, $P(B\to B)=\frac37$, y $P(B\to C)=\frac1{14}$.

Si dejamos $E_A$ ser el esperado número de movimientos para llegar desde $A$ $C$ $E_B$ser el número esperado de movimientos de $B$$C$, podemos establecer las siguientes ecuaciones:

$E_B=\frac{1}{14}\cdot 1+\frac{3}{7}(E_B+1)+\frac{1}{2}(E_A+1)$ y

$E_A=\frac17(E_B+1)+\frac67(E_A+1)$.

Usted debe ser capaz de resolver este sistema de $E_A$ $E_B$ a acabar con el problema.