Una hormiga en un tablero de ajedrez infinito

Question

Hay un tablero de ajedrez infinito, y una hormiga $A$ está en el centro de uno de los cuadrados.

La hormiga puede moverse en cualquiera de las ocho direcciones, desde el centro de una casilla a otra. Si se mueve 1 casilla al norte, al sur, al este o al oeste; requiere $1$ unidad de energía. Si se desplaza a uno de sus vecinos diagonales (NE, NW, SE, SW); requiere $\sqrt 2$ unidades de energía. Es igualmente probable que se mueva en cualquiera de las ocho direcciones. Si inicialmente tiene $20$ unidades de energía, encuentre la probabilidad de que, después de usar la máxima energía posible, la hormiga sea $2$ unidades de su posición inicial.

Supuesto

Si en el caso de que no tenga suficiente energía para moverse en un determinado conjunto de direcciones, se moverá en cualquiera de las otras direcciones con igual probabilidad.

Abordé este problema, considerando que el caso de que finalmente termine $2$ unidades al este (podemos multiplicar por cuatro para obtener todos los casos).

Si termina $2$ unidades al este, luego $\text{Total steps to right}=2+\text{Total steps to left}$ .

De alguna manera equilibraremos estos pasos, considerando que la hormiga tiene un total de $20$ unidades de energía al inicio.

Tampoco sé cómo calcular efectivamente el espacio muestral.

Si la hormiga toma un total de $n$ pasos, de manera que mientras se toman todas las $n$ pasos es igualmente probable que se mueva en cualquiera de las ocho direcciones, entonces el espacio muestral sería $8^n$ .

Pero aquí no sabemos $n$ . Además, si la energía que queda tras el penúltimo paso es inferior a $\sqrt 2$ y más de $1$ entonces la hormiga no podrá moverse en diagonal.

No fui capaz de pensar en mucho después de esto. Se agradece la ayuda.

Answer 1

Gracias por el interesante y creativo problema.

Me dio curiosidad por saber qué tamaño podría tener el camino para Energía = 20, así que lo mapeé:

El origen es la celda verde y las posibles celdas finales son amarillas. Las celdas sobre las que tu pregunta pide porcentajes son los cuadrados naranjas.

Con problemas como estos, con un gajillón de posibilidades, me inclino mucho por el uso de un simulador.

Realicé 4 simulaciones, cada una de ellas para 100 millones de ensayos, y como las 4 dieron resultados similares, concluí que el número de ensayos para cada ejecución era lo suficientemente grande. Aquí están los resultados:

------------------------ Respuesta original fin ------------------------

Editar: Esto puede ser exagerado, pero tenía curiosidad por saber cuántos distintivo puntos de parada que había, y quería ver cómo disminuían las probabilidades a medida que el punto final se alejaba del origen.

Así que alteré la simulación de nuevo y la volví a ejecutar para 2.147.483.646 carreras, y aquí están los resultados. Los porcentajes se refieren a todas las trayectorias posibles, no sólo a la porción blanca que se muestra. Sólo muestro el corte porque considera los 161 puntos distintos (y lo hace lo suficientemente pequeño como para leerlo, pero probablemente tendrá que guardarlo en su máquina para verlo). Todos los demás puntos finales posibles son un reflejo de estos puntos.

Algunos de los posibles puntos finales alejados del origen no fueron alcanzados ni una sola vez, y algunos fueron alcanzados sólo una vez (15,10; 16,7; y 17,0)

Answer 2

Probablemente haya un enfoque elegante, pero no se me ocurre ninguno. ¡Los ordenadores al rescate! Podemos resolver exactamente $20$ generaciones de la cadena de Markov sobre los estados (x, y, energía) con sólo $37932$ operaciones de suma múltiple en $64$ -bit enteros. Obtuve la misma respuesta que achille hui : $55034198045558784/ 8^{20} \approx 4.8\% $ . Aquí hay un desglose de los caminos que se detuvieron a una distancia de $2$ por el número de movimientos diagonales:

d[0]  =      225684492800
d[1]  =     4280403359232
d[2]  =                 0
d[3]  =                 0
d[4]  =  2261233261281280
d[5]  =  5136894294884352
d[6]  =                 0
d[7]  = 23843942578520064
d[8]  = 19845792415088640
d[9]  =                 0
d[10] =                 0
d[11] =  3931022473297920
d[12] =                 0
d[13] =                 0
d[14] =    10806934634496

Por ejemplo, $2261233261281280 / 8^{20}$ es la probabilidad de detenerse a una distancia de $2$ después de realizar un total de $4$ movimientos diagonales (y $14$ movimientos no diagonales). Para explicar los ceros, $\left\lceil d\sqrt{2}\right\rceil$ debe ser par para ejecutar un número par de movimientos no diagonales y terminar en una casilla del mismo color que la casilla inicial.

Answer 3

He aquí una solución en términos de fórmulas. Mi hormiga comienza en $(0,0)$ y visita los puntos de la red.

Energéticamente la historia de la hormiga puede ser codificada como una palabra $AADADAAAD\ldots$ donde la letra $A$ denota un movimiento paralelo a uno de los ejes y $D$ un movimiento en diagonal. Las letras individuales se obtienen mediante el lanzamiento de una moneda, y la palabra termina cuando se agota la energía de la hormiga. Denota por $a$ y $d$ el número de $A$ - resp. $D$ -pasos. Entonces $$d\leq d_a:=\left\lfloor{20-a\over\sqrt{2}}\right\rfloor\ .$$ Cada palabra corresponde a un recorrido de escalera en el primer cuadrante de la $(a,d)$ -plano, como se muestra en la siguiente figura:

El camino termina en un punto rojo, donde no hay más energía para un paso adicional. En un punto azul tiene lugar la siguiente regla: Si un $D$ se lanza (con probabilidad ${1\over2}$ ) en ese momento la hormiga hace un $A$ -Muévete, no obstante. Se deduce que todos los caminos terminan en un punto rojo $(a,d_a)$ . La probabilidad $p(a)$ que el número de $A$ -se mueve es exactamente $a$ viene dada entonces por las siguientes fórmulas: $$p(a)=0\qquad{\rm if}\qquad d_a=d_{a+1}\ ;$$

$$p(a)={a+d_a\choose d_a}2^{-(a+d_a)} \qquad{\rm if}\qquad d_{a-1}>d_a>d_{a+1}\ ;$$ $$p(a)= {a+d_a\choose d_a}2^{-(a+d_a)}+{1\over2}{a-1+d_a\choose d_a}2^{-(a-1+d_a)}\qquad{\rm if}\qquad d_{a-1}=d_a>d_{a+1}\ .$$ Ahora calculamos la probabilidad $p_{20}(a)$ que la trayectoria real de la hormiga termina en $(2,0)$ Dado que hace $a$ tipo $A$ se mueve. Es fácil ver que $a$ tiene que ser incluso en tal caso. Dado $a$ Hay $h$ movimientos horizontales y $v=a-h$ movimientos verticales de la hormiga, donde $0\leq h\leq a$ . En realidad tenemos $h+d_a$ horizontal independiente $\pm1$ -pasos, que deberían sumar $2$ y $a-h+d_a$ vertical $\pm1$ -pasos, que deberían sumar $0$ . Por lo tanto, $h+d_a$ tiene que ser uniforme también. Debido a la distribución Bernoulli del $\pm1$ signos obtenemos de esta manera $$p_{20}(a)=\sum_{0\leq h\leq a, \ h+d_a\ {\rm even}}{a\choose h} 2^{-a}{h+d_a\choose (h+d_a)/2-1}\cdot{a-h+d_a\choose(a-h+d_a)/2} 2^{-(a+2d_a)}\ .$$ La probabilidad solicitada $p$ por lo tanto, viene a $$p=4\sum_{0\leq a\leq 20, \ a\ {\rm even}} p(a)\>p_{20}(a)\ .$$ El cálculo dio como resultado $$p={26872167014433\over562949953421312}\doteq0.0477346\ .$$

Answer 4

Esto es lo suficientemente pequeño como para poder enumerar las posibilidades.

Para resolver el subproblema, en algún punto de la secuencia se necesitan 2 izquierdas $p=\frac{1}{64}$ y $c=2$ o 2 diagonales $p=\frac{2}{64}$ y $c=2\sqrt2$ .

También es necesario que haya un número par de otros movimientos que se anulen $p=\frac{1}{8}$ y $c=2$ o $c=2\sqrt2$ y las diagonales son tan probables como las ortogonales.

Si todas las jugadas son ortogonales puede haber un máximo de 10 parejas (contando las 2 izquierdas) si todas son diagonales entonces el máximo es 7.

¿Cuáles son las combinaciones?