¿Cuál es la Probabilidad de que un Caballero se queda en el tablero, después de N saltos?

Question

Decir $8 \times 8$ tablero de ajedrez como por la imagen.

Una posición es representada aquí por las coordenadas $(x,y)$.

Un movimiento es también considerado como válido, donde el Caballero de las tierras fuera del tablero de ajedrez [ Por ejemplo. de $(3,2)$ hacia $(3,1)$ pero termina fuera de ajedrez de la junta. ]

Pero una vez fuera, no puede regresar.

Pregunta:

Caballero comienza a partir de $(0,0)$. ¿Cuál es la Probabilidad de que un Caballero se queda en el tablero, después de N saltos?

Solución De Espera:

No quiero resultado exacto como $ \frac{12}{64} $ pero necesito tu ayuda en

una. el pensamiento/procedimiento/metodología a encontrar con

b. Conclusión las fórmulas en términos de permutación y combinación,

Bueno, mi pensamiento:

1. Después de $(N-1)$th mover, si Kngiht se entre $(x,y)$ donde$3 \le x \le 6$$3 \le y \le 6$, entonces el siguiente movimiento yo.e $n$th movimiento debe garantizar el caballero va a ser dentro de un tablero de ajedrez. Podría ser mi pensamiento es totalmente equivocado, ya que trata de encontrar "debe estar dentro de tablero de ajedrez"

2. En cualquier $5 \times 5$ sub parte con el Caballero de en medio, se ha $8$ movimientos posibles. Si la posición inicial es $(0,0)$ de los $8$ se tiene la opción de $2$ sólo la satisfacción de que "dentro de un tablero de ajedrez" de la restricción. Jugada siguiente, estoy perdido! Por favor me ayudan a pensar .

3. ¿Por qué no puedo, lo tratamos como:

     a. The question is valid only if N-1 moves already done with the Knight on board.
   
     b. Now to find Nth move s.t Knight hops out of board - say probability P(out)
   
     c. 1 - P(out) now gives the answer
   

   { En el Caso b la podemos utilizar algunas estadísticas como las siguientes:

       Legal moves -> L      Illegal moves -> I
   1. for 16 positions enclosed by {3c - 3f - 6c -6f} : 16 x 8 L
   2. for each 4 positions {2b,2g,7b,7g} : 4L, 4I  =>  16L , 16I 
   3. for each 16 positions  {7c-7f ,  2c-2f, 3b-6b, 3g-6g } : 6L,2I => 96L,32I
   4. for each 4 corners: 2L,6I => 8L, 24I
   5. for each 8 positions {7a,8b , 8g,7h , 2h,1g , 1b,2a} : 3L,5I => 24L,40I
   6. for each 16 positions  {3a-6a ,  3h-6h, 8c-8f, 1c-1f } : 4L,4I => 64L,64I
   

   }

Answer 1

El problema es que una cadena de Markov, y podemos atacar con álgebra lineal!

En primer lugar, podemos simplificar el problema mediante la explotación de la simetría de ambos, el caballero del movimiento y el tablero de ajedrez. Vamos a añadir la siguiente regla:

• Después de cada movimiento, el caballero se refleja en todos los horizontales, verticales y diagonales, ejes de simetría, hasta que se apoye en la parte superior izquierda del triángulo de $10$ plazas.

En otras palabras, las posiciones jurídicas son 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d y 4d. Puede visualizar estos puestos, ocupando uno de los $8$ triángulos en este diagrama:

Ahora, hay $11$ posiciones que el caballero puede ocupar después de un movimiento: el $10$ posiciones que acabamos de mencionar, y $1$ posición de la representación no-en-la-junta. Para $i,j\in[1,11]$, vamos a $P_{i,j}$ la probabilidad de transición de $i$$j$. Hay $11\times11=121$ de probabilidades a calcular, y sospecho que esta parte debe ser hecho a mano.

Ahora tenemos una $11\times11$ matriz cuadrada $P$. Para todos los $n$, la matriz de potencia $P^n$ es la matriz de transición para $n$ se mueve! Por lo tanto, vamos arbitrariamente índice de la inicial de la plaza de la $i=1$ y la posición de la junta directiva como $j=11$. Entonces la probabilidad de salir de la junta después de $n$ mueve es $(P^n)_{1,11}$, y la probabilidad de permanecer en el tablero es: $$1-(P^n)_{1,11}$$ Eso es lo máximo que puedo tomar. Usted podría expresar esta fórmula de manera más explícita, mediante el cálculo de $P$ y, a continuación, encontrar su forma normal de Jordan. Entonces usted tendrá una fórmula para las potencias $P^n$, y usted puede sacar cualquier elemento de la matriz que desea. Si has visto la fórmula explícita de los números de Fibonacci, es el mismo principio, pero con un mayor tamaño de la matriz!

Edit: Le he comentado que si el caballero está en el centro de la tabla, entonces no puede salir de la junta en $1$ mover. Esta es una útil obvservation. Si nos las posiciones de índice 3c, 3d y 4d como $i=8,9,10$, después nos dice que $P_{8,11}=P_{9,11}=P_{10,11}=0$. Así que usted puede ver, la matriz $P$ puede representar casi todo lo que sabemos sobre el problema.

Otro ejemplo de lectura de la información de $P$: Usted tiene una regla que si el caballero abandona la junta, no puede volver. Esto se traduce en la afirmación de que $P_{11,11}=1$, y para todos los $j<11$, $P_{11,j}=0$. Entre este párrafo y en el párrafo anterior, ya sabemos $14$ elementos de la matriz. Hay sólo $107$ más para calcular...

Edit 2: Otro ejemplo. Usted comentó que a partir de la posición inicial, sólo $2$ $8$ movimientos posibles estancia en el tablero. Que nos dice que $P_{1,11}=3/4$. El caballero puede permanecer en la junta de mudarse a 2c o 3b. En mi esquema, 3b se refleja de vuelta a 2c. Así que si nosotros índice 2c$j=6$,$P_{1,6}=1/4$. Para todos los otros $j$ además $6$$11$,$P_{1,j}=0$. Esa es otra de las $11$ elementos de la matriz calculada; $96$ ir...

Answer 2

Como se ha mencionado por Chris Culter, el cálculo es un poco tedioso. Siguientes Chris y el etiquetado de los 64 campos, así como para hacer las simetrías explícita, e.g:

$$ 0 \ \ 7 \ \ 6 \ \ 3 \ \ 3 \ \ 6 \ \ 7 \ \ 0 \\ 7 \ \ 9 \ \ 1 \ \ 5 \ \ 5 \ \ 1 \ \ 9 \ \ 7 \\ 6 \ \ 1 \ \ 8 \ \ 4 \ \ 4 \ \ 8 \ \ 1 \ \ 6 \\ 3 \ \ 5 \ \ 4 \ \ 2 \ \ 2 \ \ 4 \ \ 5 \ \ 3 \\ 3 \ \ 5 \ \ 4 \ \ 2 \ \ 2 \ \ 4 \ \ 5 \ \ 3 \\ 6 \ \ 1 \ \ 8 \ \ 4 \ \ 4 \ \ 8 \ \ 1 \ \ 6 \\ 7 \ \ 9 \ \ 1 \ \ 5 \ \ 5 \ \ 1 \ \ 9 \ \ 7 \\ 0 \ \ 7 \ \ 6 \ \ 3 \ \ 3 \ \ 6 \ \ 7 \ \ 0 \\ $$ de ello se desprende que las probabilidades de que el caballero en el paso de tiempo $n+1$ a estar en cada uno de los campos marcados con los números $0,1,2,..,9$ puede ser expresada a través de: $$\begin{pmatrix}p_0^{(n+1)}\\p_1^{(n+1)}\\p_2^{(n+1)}\\p_3^{(n+1)}\\p_4^{(n+1)}\\ p_5^{(n+1)}\\p_6^{(n+1)}\\p_7^{(n+1)}\\p_8^{(n+1)}\\p_9^{(n+1)}\end{pmatrix} = \frac{1}{8} \begin{pmatrix}0&1&0&0& 0 & 0 & 0 & 0 & 0 & 0\\ 1&0&1&1&1&1&1&0&0&0\\ 0&1&0&0&1&1&0&0&2&0\\ 0&1&0&0&1&0&0&0&1&1\\ 0&1&1&1&2&1&1&0&0&1\\ 0&1&1&0&1&0&1&1&1&0\\ 0&1&0&0&1&1&0&1&0&0\\ 0&0&0&0&0&1&1&0&1&0\\ 0&0&2&1&0&1&0&1&0&0\\ 0&0&0&1&1&0&0&0&0&0\end{pmatrix} \begin{pmatrix}p_0^{(n)}\\p_1^{(n)}\\p_2^{(n)}\\p_3^{(n)}\\p_4^{(n)}\\ p_5^{(n)}\\p_6^{(n)}\\p_7^{(n)}\\p_8^{(n)}\\p_9^{(n)}\end{pmatrix}$$

con $p_0^{(0)}=1/4$ $p_i^{(0)}=0$ todos los $i>0$.

La probabilidad solicitada por el caballero de la junta después de $n$ mueve es igual a la suma de $$4p_0^{(n)}+8p_1^{(n)}+4p_2^{(n)}+8p_3^{(n)} +8p_4^{(n)}+8p_5^{(n)}+8p_6^{(n)}+8p_7^{(n)}+4p_8^{(n)}+4p_9^{(n)}$$ Para un gran $n$ esta probabilidad disminuye con cada movimiento por un factor igual a la del mayor autovalor de la anterior matriz.

Answer 3

Desde ya 0,0 6 de los 8 movimientos de final de la junta
De los dos restantes se mueve en 2 de los 8 de final de la junta
Que debe darle ya un buen indicador de lo difícil que puede ser para mantener el caballo en el tablero.