Dado un caballo en un tablero de ajedrez infinito que se mueve al azar, ¿cuál es el número esperado de casillas distintas que alcanza en 50 movimientos?

Question

Me preguntaron esto en una entrevista y no estaba seguro de cómo enmarcar la respuesta. Básicamente, como en la pregunta, tienes un caballo en un tablero de ajedrez infinito y elige uno de sus 8 movimientos válidos uniformemente en cada movimiento. Después de 50 movimientos, la pregunta era dar (lo más ajustado posible) un límite inferior y superior del número esperado de casillas distintas que alcanzó.

Llegué a darme cuenta de que el caballo debe vivir en una casilla de 200x200, y que sólo puede llegar a la mitad de las casillas (ya que debe terminar en el mismo color en que empezó). Sin embargo, esto no aborda realmente el aspecto aleatorio de la pregunta.

Answer 1

Se puede obtener una solución exacta calculando $d_{x, y}(n)$ que es el número de caminos distintos que llegan a $(x, y)$ por primera vez después de $n$ pasos. El número total de caminos $p_{x,y}(n)$ que contiene $(x, y)$ después de $n$ pasos entonces tiene relación:

$$p_{x, y}(n) = 8p_{x, y}(n-1) + d_{x, y}(n)$$

Utilizando esto podemos expresar el número esperado de casillas distintas por camino después de $n$ pasos, ya que el recuento del número total de cuadrados distintos para cada trayectoria y el número total de trayectorias distintas que cruzan un cuadrado son equivalentes al sumar sobre todas las trayectorias o todos los cuadrados.

Entonces, ahorrando algo de tiempo de cálculo, encontramos por simetría rotacional cuádruple que el número esperado de cuadrados distintos por camino después de $n$ pasos equivale a:

$$1 + \frac{4}{8^{n}}\sum_{(x > 0, y \geq 0)} p_{x, y}(n)$$

¿Cómo calculamos $d_{x, y}(n)$ ? Lo hacemos mediante matrices $M_{x, y}(n)$ que son inicialmente cero en todas partes excepto en $(0, 0)$ donde tienen valor $1$ . A continuación, aplicamos una convolución de núcleo que codifica los posibles movimientos del caballo:

$$M'_{x, y}(n)=\begin{bmatrix}0&1&0&1&0\\ 1&0&0&0&1\\ 0&0&0&0&0\\ 1&0&0&0&1\\ 0&1&0&1&0\\\end{bmatrix}\star M_{x, y}(n-1)$$

Entonces $d_{x, y}(n)$ es el elemento en $(x, y)$ en $M'_{x, y}(n)$ y establecemos $(x, y)$ en la matriz anterior a cero para obtener $M_{x, y}(n)$ para futuros cálculos. Como ponemos repetidamente ese coeficiente a cero después de cada iteración es que contamos el número de caminos distintos que llegan a $(x, y)$ para el primero tiempo, en lugar de todos los caminos que llegan $(x, y)$ después de $n$ pasos. Lamentablemente, esto significa que para todos los posibles $(x, y)$ debemos calcular estas matrices un total de $n$ tiempos.

He implementado lo anterior en Rust:

use gmp::mpz::Mpz;
use gmp::mpq::Mpq;
use rayon::prelude::*;

fn knight_step(d: Vec<Mpz>, w: i32) -> Vec<Mpz> {
    let mut nd = vec![Mpz::new(); (w*w) as usize];
    for &(dx, dy) in &[(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)] {
        let rx = (-dx).max(0)..(w-dx).min(w);
        let ry = (-dy).max(0)..(w-dy).min(w);
        for x in rx {
            for y in ry.clone() {
                let cx = x + dx;
                let cy = y + dy;
                nd[(x*w + y) as usize] += &d[(cx*w + cy) as usize];
            }
        }
    }

    nd
}

fn count_distinct(n: usize) -> Mpz {
    let w = 4*n + 1; // Size of a side of the board.
    let z = 2*n; // Origin is at (z, z);

    let mut total_distinct = Mpz::new();
    for x in z+1..w {
        println!("{}", x);
        let subproblems: Vec<_> = (z..w).collect::<Vec<usize>>().par_iter().map(|y| {
            let mut d = vec![Mpz::new(); w*w];
            d[z*w + z] = Mpz::from(1);
            let mut p = Mpz::new();

            for _ in 0..n {
                d = knight_step(d, w as i32);
                p = 8i64*p + &d[x*w + y];
                d[x*w + y] = 0.into();
            }

            p
        }).collect();

        for s in &subproblems {
            total_distinct += 4i64*s;
        }
    }

    total_distinct
}

fn main() {
    let n = 50;
    let q = Mpq::ratio(&count_distinct(n), &Mpz::from(8).pow(n as u32));
    println!("{}", q + &1.into());
}

Dando el resultado exacto:

$$\frac{455207943209697100946821497094086408107332219}{11150372599265311570767859136324180752990208} \approx 40.82446$$

Answer 2

Mis experimentos en Mathematica dan $40.06$ como el número medio de celdas distintas (he hecho varios intentos para $100'000$ ensayos).

Sin embargo, cuento el cuadrado inicial porque hace que el programa sea más sencillo.

No sabría cómo enfocar este problema teóricamente, pero es lo suficientemente sencillo como para hacer pruebas. Los movimientos del caballero lo cambian $2$ células en una dirección y $1$ célula en la otra dirección. Lo que nos da $8$ opciones en un tablero infinito.

Aquí está el código que he utilizado y una muestra de los resultados:

Tm = 100000;
Ds = Table[1, {t, 1, Tm}];
Do[
  Nm = 50;
  P = Table[{0, 0}, {n, 1, Nm}];
  M = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 
     1}, {-2, -1}};
  Do[R = RandomInteger[{1, 8}];
   P[[n + 1]] = P[[n]] + M[[R]], {n, 1, Nm - 1}];
  Ds[[t]] = CountDistinct[P], {t, 1, Tm}];
Histogram[Ds]
N[Mean[Ds], 10]

Obsérvese que la distribución es asimétrica.

Aumentar el número de pasos para $100$ Me muevo por $77.36$ . Lo que concuerda bien con el $4/5$ relación.

Hecho $1'000'000$ pruebas con $100$ pasos y consiguió $77.38$ Así que las cifras no cambian mucho para las muestras más grandes.

Me pregunto cómo podemos conseguir el $4/5$ estimar teóricamente.

---

En general, esto entra en el tema de las caminatas aleatorias y sus probabilidades de retorno.

---

Editar Sería mejor establecer $N_m=51$ en mi programa, entonces corresponde a $50$ movimientos y la media resultante $40.82$ encaja bien con la otra respuesta.