El ratón de Markov y el laberinto

Question

Hace poco empecé a aprender sobre las cadenas de Markov y tuve un problema relacionado con el tiempo esperado de absorción:

El problema:

Markov tiene un ratón no entrenado que coloca en un laberinto. El ratón puede moverse entre habitaciones contiguas, o permanecer en la misma habitación en cualquier paso de tiempo. A la salida del laberinto hay un enorme trozo de queso sin olor del que el ratón puede salir y no volver nunca. Dada la siguiente matriz de transición:

$$\begin{pmatrix}\frac 1{10}&\frac 3{10}&\frac 35&0&0&0\\\frac 12&\frac 12 &0&0&0&0\\\frac 3{10}&0&\frac 1{10}&\frac 35&0&0\\0&0&\frac 3{10}&\frac 1{10}&\frac 3{10}&\frac 3{10}\\0&0&0&\frac 12&\frac 12&0\\0&0&0&0&0&1\\ \end{pmatrix}$$

(a) ¿Cuál es la probabilidad de que salga del laberinto, dado que comenzó en el estado $i \quad \forall \ i \in[0,5]$ ??

(b) Cuánto tiempo falta para que salga del laberinto, dado que comenzó en el Estado $i \quad \forall \ i \in[0,5]$ ?

Mi intento:

Bueno primero hice un diagrama para tener la comprensión del problema visualmente. Reemplazo el número de Estados por letras, es decir, Estado $1$ como Estado $A$ etc. y anotamos las probabilidades de transición de la matriz.

(a) Creo que como existe un estado absorbente en la salida, entonces la probabilidad de salir debe ser $1$ a.s. .

(b) Utilicé el Análisis de Primer Paso para encontrar el tiempo esperado para cada $i$ .

Dejemos que $v_i$ sea el tiempo previsto para salir de la posición inicial $i$ es decir $v_i =\Bbb E_i[T_{\{5\}}]$ . A continuación, resolver el sistema de ecuaciones:

$$\left\{ \begin{array}{ll} v_A &=1+\frac 1{10} v_A+\frac 3{10} v_B+\frac 35 v_C \\ v_B &=1+\frac 12 v_A +\frac 12 v_B\\ v_C &=1+\frac 3{10} v_A+\frac 1{10} v_C+\frac 35 v_D \\ v_D &=1+\frac 3{10} v_C+\frac 1{10} v_D+\frac 3{10} v_E+\frac 3{10} v_F \\ v_E &=1+\frac 12 v_D+\frac 12 v_E\\ v_F &=0 \end{array} \right.$$

Así que obtengo la siguiente solución: $$\Bbb E_A[T_{\{5\}}]=14; \quad \Bbb E_B[T_{\{5\}}]=16 \quad \Bbb E_C[T_{\{5\}}]=11 \frac 13 \quad \Bbb E_D[T_{\{5\}}]=8 \frac 13 \quad \Bbb E_E[T_{\{5\}}]= 10 \frac 13$$

No soy $100\%$ seguro sobre la parte (b).

Mi(s) pregunta(s):

Me preguntaba, ¿hay otra forma de ver este problema sin utilizando las cadenas de Markov o el análisis de primer paso? Siento que hay variables aleatorias geométricas involucradas aquí.

También qué pasaría si hubiera 2 salidas, ¿podría aplicar exactamente los mismos principios o hay algo que cambia?

Gracias de antemano.

Answer 1

Este es otro enfoque:

Un paseo aleatorio por un grafo conectado, no dirigido y no ponderado pasa el mismo tiempo en cada arista en cada dirección. Así, la proporción de tiempo que pasa en un vértice es el número de aristas que inciden en el vértice dividido por el doble del número total de aristas. Esto sigue siendo cierto si se ponderan las aristas e incluso si el paseo es periódico. Se puede comprobar todo esto verificando que las distribuciones correspondientes son invariantes bajo transiciones (donde las probabilidades de transición son proporcionales a los pesos de las aristas).

En su caso, necesitamos bucles propios en el gráfico, lo que complica las cosas, pero sólo ligeramente. Un bucle propio sólo tiene una "dirección", por lo que sólo cuenta una vez en la suma de los pesos de las aristas, mientras que las aristas normales cuentan dos veces.

El tiempo de retorno esperado de un vértice (el tiempo que tarda el paseo aleatorio que parte del vértice en volver a él, posiblemente de forma inmediata a través de un bucle propio) es el recíproco de la proporción de tiempo que el paseo pasa en el vértice.

¿Qué tiene que ver todo esto con su problema? Añade un vértice para la salida y asigna pesos de aristas a las puertas para que den su matriz de transición. Si asignas pesos $3$ al bucle propio en $B$ para que todos los pesos de los bordes salgan como enteros, puedes trabajar desde $B$ a través del laberinto para llegar a estos pesos de borde:

Los números en las puertas son los pesos de los bordes propios, los números junto a las etiquetas de las habitaciones son los pesos de los bucles propios. La suma (con los bucles propios contados una vez y los bordes propios contados dos veces) es $112$ .

El tiempo de retorno para un paseo aleatorio en este gráfico que comienza en la salida es $1$ más el tiempo de salida $v_D$ de $D$ . Así,

$$v_D=\frac{112}{12}-1=8\frac13\;,$$

de acuerdo con su solución.

Consideremos ahora el subgrafo que comprende los vértices $A$ a través de $D$ pero sin el bucle propio en $D$ . La suma de los pesos de las aristas con multiplicidades es $48$ . El tiempo de retorno de un paseo aleatorio por este subgrafo partiendo de $D$ es $1$ más el tiempo previsto para llegar desde $C$ a $D$ . Así,

$$v_C=v_D+\frac{48}{12}-1=11\frac13\;,$$

de nuevo de acuerdo con tu solución. Creo que puedes resolver el resto por ti mismo.

Obsérvese que esto requiere que resolvamos sólo ecuaciones lineales simples, no sistemas de ecuaciones (incluyendo la parte de calcular los pesos de las aristas). Esto funciona siempre que el ratón esté en un árbol.

Answer 2

Tu solución nos vale, funcionaría igual para dos salidas y otras aproximaciones llevarían a un cálculo equivalente porque al final obtendrás las soluciones de este sistema lineal aunque no lo escribas.