Proceso estocástico: En un tablero de ajedrez, un solo caballo aleatorio realiza un paseo aleatorio simple

Question

En un tablero de ajedrez, un solo caballo aleatorio realiza un simple paseo aleatorio. Desde cualquier casilla, el caballo elige entre sus movimientos permitidos con igual probabilidad. Si el caballo comienza en una esquina, ¿cuánto tiempo, en promedio, tardará en volver a esa esquina?

---

Entiendo la pregunta. Sé que desde la esquina el caballo tiene dos opciones de casillas. Desde las dos casillas la pieza tiene 5 direcciones (para cada ubicación), etc.

El caso es que quiero crear una matriz de transición para esta cadena de Markov. Pero no se me ocurre cómo hacerlo sin que cada cuadrado represente un estado distinto..lo que haría es una matriz de transición de 64x64.

Estoy seguro de que estoy complicando demasiado este problema, pero ¿alguien tiene algún consejo sobre cómo avanzar? Si puedo crear la matriz de transición entonces puedo hacer de la esquina un estado absorbente y seré de oro para avanzar.

Answer 1

Sí, se puede simular utilizando una gran matriz de transición y hacerla rodar, mientras se observa la probabilidad acumulada de saltar de nuevo a la esquina, un estado absorbente. Se trata de una travesía de Markov en un grafo con 64 nodos y un montón de lados, cada uno de los cuales representa un movimiento permitido de un caballo en un tablero.

La media es sorprendentemente alta: 168. Esta cantidad de pasos en promedio es la longitud del ciclo en este gráfico cuando se comienza en la esquina.

Aquí está la solución en Python:

import numpy as np

def jump(i,j):
   "true if jump is allowed"
   ret = (abs(i) == 2 and abs(j) == 1) or (abs(i) == 1 and abs(j) == 2)
   return ret

# init state after 1st jump
s1 = np.zeros(64) # state after 1st jump

for i in range(8):
    for j in range(8):
        if jump(i,j):
            s1[i*8 + j] = 1
s1 = s1 / np.sum(s1)
# print(np.reshape(s1,(8,8)))           

p = np.zeros((64,64)) # transition matrix, where state num k = 8 * i + j

# init tx matrix
for ki in range(8):
    for kj in range(8):
        k = ki*8 + kj
        for i in range(8):
            for j in range(8):
                if jump(ki-i,kj-j):
                    p[k, i*8 + j] = 1
        p[k, :] = p[k, :] / np.sum(p[k, :])
        # print(ki,kj,np.reshape(p[k,:],(8,8)))
p[0,:] = np.zeros(64)
p[0,0] = 1
# print(0,0,np.reshape(p[0,:],(8,8)))

steps = 10000
cumps = np.zeros(steps) # cumulative probability of each cycle length

s = s1
for step in range(2,steps):
    s = np.matmul(s, p)
    cumps[step] = s[0]
#    print(step, ps[step])
ps = np.diff(cumps) # probability of a step
print("check add up to 1: ",cumps[steps-1])
print("mean steps: ",np.dot(range(1,steps),ps))

import matplotlib.pyplot as plt

# plt.plot(range(1,1001), ps[0:1000])
plt.plot(range(1,1001), cumps[1:1001])
plt.xlabel("cycle length")
plt.ylabel("probability")
plt.title("CDF")
plt.show()