Cadena de Markov (absorción)
Acabo de comenzar a aprender la cadena de Markov y no tengo ni idea de cómo resolver este problema.
Un hombre sube una roca por una colina de 40 metros de altura. Cada minuto, con probabilidad de 1/3, logra rodar la roca 1 metro hacia arriba, mientras que con probabilidad de 2/3 la roca rueda 1 metro hacia abajo. Si el hombre se encuentra actualmente a mitad de camino hacia la cumbre, ¿cuál es la probabilidad de que llegue a la cumbre antes de descender a las estribaciones?
Respuestas
Sería exagerado resolver este problema utilizando la teoría de la cadena de Markov: pero los conceptos subyacentes te ayudarán a enmarcarlo de una manera que admita una solución simple.
Formular el problema
El concepto más fundamental es el de un estado: podemos modelar esta situación en términos de 41 posiciones distintas, o "estados", situados a intervalos de un metro de altura desde la parte inferior (altura -40) hasta la parte superior (altura 0) de la colina. El estado actual, a la mitad de la colina, tiene una altura de -20.
El segundo concepto fundamental es el de la independencia de los eventos pasados: la posibilidad de lo que suceda a continuación depende solo del estado, no de los detalles de cómo llegó el hombre allí. En consecuencia, la posibilidad de llegar a la cumbre depende solo del estado. En consecuencia, si escribimos$s$ para un estado, la posibilidad de alcanzar la cumbre se puede escribir simplemente $p(s).$ Se nos pide que encontremos $p(-20).$
De cualquier estado $s$ Entre $-40$ y $0$ hay un $1/3$ posibilidad de que $s+1$ será el próximo estado y un $2/3$ posibilidad de que $s-1$será el próximo estado. Las leyes más básicas de probabilidad condicional implican
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
El paso final de la formulación del problema trata los puntos finales o "estados absorbentes" $s=0$ y $s=-40.$ Debe quedar claro que
$$p(0)=1;\ p(-40)=0.\tag{**}$$
Análisis
En este punto, el trabajo puede parecer formidable: ¿quién quiere resolver una secuencia de 40 ecuaciones? Un buen método de solución combina todas las ecuaciones en un solo objeto matemático. Pero antes de continuar, permítame comentarle que no necesita seguir este análisis: bastará con comprobar que la fórmula final (resaltada a continuación) satisface todas las condiciones establecidas por el problema, y esto es solo una cuestión de álgebra simple.
En esta coyuntura, es útil resolver el problema general. Supongamos que hay una secuencia de estados$s=0,1,2,\ldots, n$ y que cada estado $s$ Entre $1$ y $n-1$ transiciones a $s-1$ con probabilidad $p$ y para $s+1$ con probabilidad $1-p.$ Para todos $s$ dejar $a_s$ ser la posibilidad de llegar al estado $0$ antes de golpear el estado $n.$ (He dejado caer el anterior "$p(-s)$"notación porque conduce a demasiadas p y he pasado de indexar estados con números negativos a indexarlos con números positivos).
Como hemos visto, $a_0=1,$ $a_n=0,$ y de otra manera $a_{s} = pa_{s-1} + (1-p)a_{s+1}$(la "relación de recurrencia"). Este conjunto de ecuaciones está claramente codificado por un polinomio
$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$
Conectando la relación de recurrencia y luego recolectando poderes comunes de $t$ (escritura $a_{n+1}=0$ por conveniencia) da
$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$
Esta es una sola ecuación para el polinomio$P$ (al menos hasta $t^n;$ Ignoraré cualquier coeficiente de $t^n$o potencias más altas que podrían ser necesarias para hacer que la ecuación funcione exactamente.) Simplifique un poco esta ecuación usando la condición inicial $a_0=1$ y resolver para $P$ Llegar
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
Ahora cada coeficiente de$P$ se puede expresar en términos del número (aún desconocido) $a_1.$ El valor de $a_1$ está determinada por la condición final $a_n=0.$
Una fórmula cerrada es posible expandiendo el lado derecho como una fracción parcial. Se trata de observar
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
y expandir las fracciones como sumas de series geométricas, ambas en la forma
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
y multiplicando eso por el numerador $(1-p) + (-1 + (1-p)a_1)t$ para obtener $P(t).$ Esto da una fórmula cerrada para cada término en $P(t)$ como una función de $a_1.$
por $p\ne 1/2$ y escribiendo $\lambda = p/(1-p)$ este enfoque da el resultado general
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
para $s=1, 2, \ldots, n$ (y esto pasa a funcionar para $s=0,$también). (Cuando$p=1/2,$ $\lambda=1$hace que esta fórmula no esté definida. Sin embargo, puede resolverlo fácilmente con una fórmula simple, tomando el límite de$a_s$ como $\lambda\to 1$ utilizando una sola aplicación de la regla de L'Hopital).
Como prueba, está claro que esta fórmula da $a_0=1$ y $a_n=0.$ Queda por verificar que satisfaga la relación de recurrencia, pero eso es cuestión de mostrar
$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$
que es sencillo.
Solicitud
En el problema dado $n=40,$ $p=1/3,$ y se nos pide que encontremos $a_{20}.$ Por consiguiente $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ y
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
La expansión en el lado derecho se puede terminar después de los dos primeros términos cuando se calcula en punto flotante de doble precisión (que tiene una precisión de $52$ lugares binarios), dando
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
un poco menos de uno en un millón.
Imagínese que el viaje de escalada consta de 41 estados, uno por cada metro posible, según los estados 0, 1, 3, ...., 40. La matriz de probabilidad de transición se convierte entonces en una matriz de 41x41, que representa las diferentes probabilidades de pasar de un estado a otro. Se parece a lo siguiente:
0 1 2 -- 40
0 0 1 0 -- 0
1 2/3 0 1/3 -- 0
2 0 2/3 0 -- 0
| | | | -- |
| | | | -- |
40 0 0 0 -- 0
Llamemos a esta matriz P. Si empezamos a 20 metros, con otras palabras en el estado 20, podemos representar esto como un vector (41 elementos largos) con las probabilidades de partida en cada estado, llamadas u, u=[0,0, ... , 0, 1, 0 ... 0, 0], donde el 1representan una probabilidad del 100% de a partir de 20 metros .
La multiplicación de matrices,, u*Pse convierte en las probabilidades de terminar en todos los demás estados en el paso de tiempo t +1. Si continuamos haciendo esta multiplicación de matrices una y otra vez, u*P^tdonde t va hacia el infinito, llegaremos a una matriz de estado estable P *. Esta matriz de estado estable representa las probabilidades de terminar en todos los demás estados.
Entonces, en su caso, haría esta multiplicación de matrices en un lenguaje de programación de su elección muchas veces (por ejemplo, 100+), y simplemente miraría hacia arriba P[20,40], lo que le daría la probabilidad de comenzar en 20 metros y hacer todo el camino en la cima de la colina!