¿usar cadenas de markov para resolver un problema de proyecto-euler?

Question

Nunca aprendí lo que es la cadena de markov, pero buscando en google parece que si hay estados finitos y cada estado tiene probabilidades de saltar a otros estados, puedo usar la cadena de markov.

Lo que estoy haciendo es http://projecteuler.net/problem=227 la persecución.

"The Chase" es un juego que se juega con dos dados y un número par de jugadores.

Los jugadores se sientan alrededor de una mesa; el juego comienza con dos jugadores jugadores opuestos con un dado cada uno. En cada turno, los dos jugadores con un dado tiran el dado. Si un jugador saca un 1, pasa el dado a su vecino de la izquierda. Si un jugador saca un 1, pasa el dado a su vecino de la izquierda; si saca un 6, pasa el dado a su vecino de la derecha; en caso contrario, se queda con el dado. derecha; en caso contrario, se queda con el dado para el siguiente turno. El juego termina cuando un jugador tiene los dos dados después de haberlos lanzado y pasado; Ese jugador ha perdido entonces.

En una partida con 100 jugadores, ¿cuál es el número esperado de turnos que el juego dura?

Indique su respuesta redondeada a diez dígitos significativos.

N personas se sientan alrededor de una mesa, así que las nombro 1, 2 ... 100 en el sentido de las agujas del reloj (o en sentido contrario, lo que no importa) la persona 1 y 51 tienen los dados al principio.

A partir de la descripción, dadas N personas, el estado (A, B) es que la persona A y la persona B tienen dados. Pueden pasar al estado(A+1, B), estado(A, B+1), estado(A+1, B+1) ... estado(A-1, B-1). Hay 8 estados distintos en los que al menos un dado cambia de propietario. Puedo calcular todos los estados siguientes y las probabilidades de los mismos para cada estado.

digamos que la probabilidad (a, b) es la probabilidad de terminar un juego si la persona a y b tiene los dados. si a=b, que es condición del juego para terminar, la probabilidad (a, b) = 1. si no a=b, hice una función para encontrar la probabilidad :

si a=b entonces devuelve 1.

si no a=b,

for each next-state from (a, b):
   add up (probability of moving to a next-state)*(probability of ending game in that state)

por lo que esta función buscará recursivamente si el juego puede terminar en ese estado.

Mi preocupación es que la función anterior podría entrar en una recursión interminable. por ejemplo -

empiezo con (1, 10) -> a partir de este estado el juego no se puede hacer en un turno, así que busco -- (0, 10), (2, 11) ... Sigo buscando hasta dar con (a, b) que a=b. digamos que estoy en medio de la búsqueda, terminé en (4, 5) y el juego puede terminarse en (5, 5). pasar de (4, 5) a (5, 5) tiene una probabilidad P. pero para una probabilidad (1-P), tengo que seguir buscando.

Creo que hay algo que me falta sobre las probabilidades o realmente no sé sobre la cadena de markov. Cualquier ayuda será apreciada.

Answer 1

@did, te agradezco mucho tu ayuda. tu idea de dividir los estados por la distancia, y no por el índice de jugadores que tienen los dados, redujo el caso de ~10000 a 51.

Al final resolví este problema. Primero, dividí cada estado del juego en la distancia entre dos dados - $d$ para la distancia, es $ 0 \le d \le 50$

Construí una tabla de probabilidad precisa para la transición entre $d_n $ a $d_m$ . Esto se puede hacer mediante una programación sencilla con sólo 50 bucles. por ejemplo, la tabla de probabilidad para $d_{29}$ es :

{27: 0.027777777777777776, 28: 0.2222222222222222, 29: 0.5, 30: 0.2222222222222222, 31: 0.027777777777777776}

que, para cada estado $d_n$ necesitamos el número esperado de jugadas para reducir la distancia entre dos dados. Esto se da como una ecuación lineal multivariable. para $d_{29}$ El $E(29)$ es : $$ E(29) = 1 + 0.02777777777777777E(27) + 0.2222222222222222E(28) + 0.5E(29) + 0.2222222222222222E(30) + 0.027777777777777776E(31) $$

y $E(0) = 0$ . con estas 51 ecuaciones, utilicé el álgebra lineal para resolver E(1) a E(50). Por cierto, las jugadas esperadas requeridas ( $E(50)$ ) era inferior a 3.800, sobre todo menos de lo que sugería.

Answer 2

Esta no es una solución completa.

Un enfoque de cadena de Markov se basa en la distancia $X_t$ de la posición del primer troquel a la posición del segundo tras $t\geqslant0$ se juegan los partidos. Con $2N$ jugadores alrededor de la mesa, $X_0=N$ , $0\leqslant X_t\leqslant N$ por cada $t\geqslant0$ y se quiere calcular la media del primer tiempo de golpeo de $0$ definido como $T=\inf\{t\geqslant0\mid X_t=0\}$ .

Dejemos que $\mathfrak X=\{0,1,\ldots,N\}$ . Para cada estado $x$ sur $\mathfrak X$ las transiciones con probabilidades positivas son de $x$ a los $x+z$ con $-2\leqslant z\leqslant2$ tal que $x+z$ está de nuevo en $\mathfrak X$ .

El siguiente paso sería escribir con precisión estas probabilidades de transición y deducir $\mathbb E(T)$ .

Un segundo enfoque consiste en contar la distancia $\bar X_t$ en el sentido de las agujas del reloj, y luego $0\leqslant \bar X_t\leqslant 2N$ y se considera $\bar T=\inf\{t\geqslant0\mid \bar X_t\in\{0,2N\}\}$ . Si el sitio $x$ está en el medio, por así decirlo, es decir, si $\bar X_t=x$ con $2\leqslant x\leqslant 2N-2$ entonces el desplazamiento se distribuye como la suma de dos variables aleatorias i.i.d. cada una con distribución $\frac16(\delta_{-1}+4\delta_0+\delta_1)$ . Por lo tanto, $\bar X_{t+1}=\bar X_t+\xi$ donde $\mathbb P(\xi=+2)=\mathbb P(\xi=-2)=\frac1{36}$ , $\mathbb P(\xi=+1)=\mathbb P(\xi=-1)=\frac8{36}$ y $\mathbb P(\xi=0)=\frac12$ .

Observando que $\mathbb E(\xi^2)=\frac23$ se ve que $M_t=\bar X_t^2-\frac23t$ es casi una martingala, por lo que una conjetura natural es que $\mathbb E(\bar T)\approx\frac32(\mathbb E(X_T^2)-N^2)$ . Desde $\bar X_T$ es uniforme en $\{0,2N\}$ por simetría, se obtiene $\mathbb E(T)\approx\frac92N^2$ .

Para $100$ jugadores, $N=50$ por lo que esta heurística sugiere que el número esperado de vueltas es $\approx11,250$ .