Cubrir el tiempo de tablero de ajedrez (el rey)

Question

Considere la posibilidad de un paseo aleatorio de un rey en un tablero de ajedrez, que a cada paso se mueve de una manera uniforme aleatorio permite la plaza. ¿Qué es exactamente la media de tiempo para visitar todos los cuadrados (cover tiempo), a partir de una esquina de la plaza?

Hay una expresión algebraica de la solución?

Answer 1

No hay en principio ninguna dificultad en responder a esta pregunta. Como señalo en mi respuesta aquí, el cálculo de la espera de la cubierta el tiempo de algunos de $\cal S$ se reduce a calcular la espera de golpear tiempo de cada posible que no esté vacía subconjunto $A$$\cal S$:

$$\mathbb{E}(\text{cover time})=\sum_A (-1)^{|A|-1} \mathbb{E}(T_A)$$

Estos golpear a veces se definen por $T_A=\inf(n\geq 0: X_n\in A)$.

---

Mirar hacia fuera abajo! Ignorantes de las reglas del ajedrez, no me di cuenta de que un rey se puede mover en diagonal. Los siguientes cálculos se basan en una pieza que puede moverse solamente en cuatro formas: norte, sur, este u oeste.

---

Sólo para ilustrar, permítanme mostrarles la solución para un $2\times 2$ tablero de ajedrez:

El tiempo de espera para cubrir las otras 3 plazas ${a,b,c}$ es igual a $$\mathbb{E}(T_{a})+\mathbb{E}(T_{b})+\mathbb{E}(T_{c})-\mathbb{E}(T_{a,b})-\mathbb{E}(T_{a,c})-\mathbb{E}(T_{b,c})+\mathbb{E}(T_{a,b,c})$$

Estándar de la cadena de Markov de la teoría de los usos de álgebra lineal para encontrar estos esperado golpear veces $$\mathbb{E}(T_{a})=\mathbb{E}(T_{c})=3, \mathbb{E}(T_{b})=4, \mathbb{E}(T_{a,b})=\mathbb{E}(T_{b,c})=2, \mathbb{E}(T_{a,c})=\mathbb{E}(T_{a,b,c})=1$$

Poniendo todo junto, nos encontramos con que la espera cubrir el tiempo es $3+3+4-2-2-1+1=6$.

Tenga en cuenta que me contó el rey de la posición inicial, como ya se ha cubierto. Si requieren un retorno a su punto de partida puede modificar la técnica anterior.

El número de términos en la suma que este método poco práctico para un $8\times 8$ tablero de ajedrez, sin embargo!

---

Agregado: Si mis cálculos son correctos, se espera que cubra el tiempo de la $3\times 3$ junta es $${140803109038245\over 4517710919176}=31.1669$$

Answer 2

No es una expresión algebraica de la solución; el promedio de la cubierta momento y desde cualquier nodo en un grafo es conocido por ser racional y puede ser encontrado en tiempo exponencial. No es probable que tenga una forma simple, sin embargo. Experimentalmente, me encontré con el siguiente código:

import random

def reachable((i,j)):
   ok = lambda(q):(min(q)>=1 and max(q)<=8)
   return filter(ok, [(i-1,j-1), (i-1,j), (i-1,j+1), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1)])

def covertime(sq, rng=random.Random()):
   seen = set([sq])
   path = [sq]
   while len(seen)<64:
      path.append(rng.choice(reachable(path[-1])))
      seen.add(path[-1])
   return len(path)-1

He encontrado que la media de la cubierta del tiempo a partir de una esquina de la plaza se acerca $597$, mientras que la media de la cubierta del tiempo a partir de un centro de la plaza era más grande, acerca de $621$.