Tenía curiosidad acerca de cómo aplicar el concepto de cadenas de Markov para el siguiente problema:
Rodando un dado, ¿cuál es la probabilidad de 1 2 a continuación ocurrirá antes de dos seises en una fila?
He probado un modelo que cuenta con 15 Estados; sin embargo, este problema parece que debería ser mucho más fácil.
Podemos resolver esto de manera gráfica. Sólo es fácil adiciones, multiplicaciones y divisiones son necesarios.
La pregunta se refiere sólo tres caras de la muerte: la 1, 2, y el 6. Al principio, ninguno de estos aspectos ha sido lanzado. Vamos a llamar a este estado S ("inicio"). Los estados que corresponda, que puede ser alcanzado a partir de ella se S (con una probabilidad de $4/6$), 1y 6 (cada uno con una probabilidad de $1/6$).
Continuar la construcción de la cadena de Markov considerando lo que puede ser alcanzado a partir de los nuevos estados que se han encontrado, 1 y 6:
De 1, podemos rodar un 1 (permanecer en el estado 1), 2 (el final de la cadena con el estado 12, que es uno de los estados que estamos buscando), 6 (con lo que se mueve en estado 6) o de vuelta a S lo contrario. Las posibilidades son todas las $1/6$ durante los tres primeros movimientos, dejando un resto $1-3\times 1/6=1/2$, para tener la oportunidad de regresar a S.
De 6, se puede entrar a los estados 1, 66o S , con posibilidades $1/6$, $1/6$, y (por tanto) $2/3$, respectivamente.
El único de los nuevos estados a tener en cuenta son los estados del terminal 12 y 66. Por lo tanto, se han generado todos los estados de la cadena (y se calculan sus probabilidades de transición cuando lo hicimos). Aquí es una imagen gráfica que muestra los estados de los nodos y las transiciones como se indica bordes (o "pipes"), marcado por sus probabilidades.
Probabilidad fluye como una conserva de líquido a través de esta canalización. (Esto es solo una manera intuitiva para reafirmar los axiomas de la probabilidad.) En última instancia, queremos saber ¿qué fracción de líquido que entra en el punto S es 12 (y la fracción restante es 66). Todo lo que tenemos que hacer es seguir la pista de. Voy a mostrar cómo hacerlo mediante la eliminación de puntos intermedios y la combinación redundante tuberías hasta que el diagrama es tan simple que puede leer la respuesta directamente de ella.
Podemos eliminar el nodo S señalando que cualquier "probabilidad de fluidos" no va a quedarse por un tiempo (que sufre S a S transiciones), pero finalmente terminará en cualquiera de los casos 1 o estado 6. La relativa probabilidades de que esos son los relativos probabilidades de las transiciones, $1/6$ dividido por $1/6+1/6$: cada uno es igual a $1/2$. Por lo tanto, si queremos hacer una transición de la 1 a S (lo cual ocurre con probabilidad de $3/6$), luego la mitad del tiempo que va a acabar a la derecha de nuevo en 1 y la otra mitad del tiempo que vamos a terminar en 6. Consideraciones similares causar dos tuberías nuevas para ser construido en el lugar de S para llevar probabilidad de 6 a 1 y 6 de nuevo a sí mismo. Estas cuatro nuevas tuberías se muestran con líneas punteadas en la parte izquierda de la figura siguiente.
Podemos combinar la probabilidad de los flujos entre los dos nodos que se producen en varios tubos: sustituir por un único tubo con la suma de los flujos. Esto se muestra a la derecha. Como un recordatorio de donde los números se originan, no he hecho toda la aritmética.
La misma idea se aplica a la auto-transiciones en los nodos 1 y 6. Por ejemplo, cualquier probabilidad de que llegue a 1 permanecerá en 1 por un tiempo, pero con el tiempo algunos de fluirá al nodo 6 y algunos de los que se va a ir a 12. Las proporciones relativas se $1/6+3/12=5/12$ a un nodo 6 y $1/6$ a un nodo 12, en proporciones $5:2$. Después de la eliminación de la 6 a 6 transición obtenemos el siguiente diagrama:
En esta coyuntura, podemos dividir el diagrama en dos partes, de nuevo, eliminando los viajes de ida y vuelta. Comenzando en el nodo 1, podemos preguntarnos cuál es la proporción de la probabilidad termina en 12. El gráfico muestra que la probabilidad de los flujos directamente a 12, o de lo contrario los flujos de 6, punto en el cual la $3/4$ de la brevedad de las devoluciones. El resto de los $1/4$ va a terminar para siempre en 66. Después de aplicar el mismo razonamiento al nodo 6, para determinar qué proporción de su probabilidad termina en 66, obtenemos estos dos parciales separados gráficos:
Finalmente, la eliminación de la auto-transiciones como antes, que, literalmente, ver el siguiente:
Los flujos con las tasas de $2/7$ $1/4\times 5/7$ 1 están en proporción $8:5$. Por lo tanto, $8/(8+5)=8/13$ de la probabilidad en 1 termina en 12. El resto, $5/13$, debe terminar en 66.
Los flujos con las tasas de $1/4$ $2/7\times 3/4$ 6 están en proporción $7:6$, de donde $7/13$ de la probabilidad en 6 termina en 66 y el restante $6/13$ termina en 12.
Que (obviamente) la medida en que podamos ir en la reducción de la gráfica original. Recuerdo, ahora, que con toda probabilidad comienza a S. Cuando hemos eliminado, se tenía que dirigir la mitad de la probabilidad de a 1 y la mitad de la probabilidad de a 6. En consecuencia, la proporción que termina en 12 es la mitad de la proporción de llegar a 12 de 1 más de la mitad de la proporción de llegar a 66 de 6:
$$\Pr(\text{12 is final state}) = \frac{1}{2}\times \frac{8}{13} + \frac{1}{2}\times \frac{6}{13} = \frac{7}{13}.$$
This is the answer: there is a $7/13\aprox 0.53846$ chance that 12 is encountered before 66.
(Either by carrying out a parallel calculation, or noting that eventually all the probability reaches either 12 or 66, we conclude that $6/13$ de la época, 66 es el estado final.)
Mirando hacia atrás en el diagrama original de la cadena de Markov, ahora podemos ver por qué 12 es ligeramente favorecido. El gráfico es casi simétrica (identificando 1 con 6 y 12 con 66), excepto que el auto transición de la 1 a 1 hace más de probabilidad para recoger a y residir en el nodo 1. En consecuencia, un poco más de ella fluye a 12 (lo que sólo puede ser alcanzado a través de la 1) de los flujos de 66 (lo que sólo puede ser alcanzado a través de la 6).
Definir los estados 1,2,3,4,5,6,2 a,6a, donde los estados 2a y 6a, absorbiendo, y todos los otros estados no absorbentes. Estado 1 puede pasar igual de probable que un 1,2,3,4,5,6. Los estados 2,3,4,5 puede pasar igual de probable que los estados 1,2,3,4,5,6. Estado 6 puede pasar igual de probable que 1,2,3,4,5,6 una. 2a transiciones a la 2a y 6a sólo las transiciones a la 6a. Editar (dos frases siguientes añadido para mayor explicación): Si el estado 2a es alcanzado, "1,2" gana, y el juego es más, con la cadena de quedarse para siempre en ese estado. Si el estado 6a es alcanzado, "6,6" gana, y el juego es más, con la cadena de quedarse para siempre en ese estado.
Por lo tanto, el paso de la matriz de transición, con los estados ordenó 1,2,3,4,5,6,2 a,6a, es
$P =$
0.1667 0 0.1667 0.1667 0.1667 0.1667 0.1667 0
0.1667 0.1667 0.1667 0.1667 0.1667 0.1667 0 0
0.1667 0.1667 0.1667 0.1667 0.1667 0.1667 0 0
0.1667 0.1667 0.1667 0.1667 0.1667 0.1667 0 0
0.1667 0.1667 0.1667 0.1667 0.1667 0.1667 0 0
0.1667 0.1667 0.1667 0.1667 0.1667 0 0 0.1667
0 0 0 0 0 0 1.0000 0
0 0 0 0 0 0 0 1.0000
El 0.1667 entradas son en realidad 1/6, y evaluados a plena de doble precisión en mis cálculos a continuación.
El estado inicial de distribución (después de un rollo) puede ser tomado como estado inicial s = [1/6 1/6 1/6 1/6 1/6 1/6 1/6 0 0]. A continuación, mira la 2a y 6a entradas de $s P^n$ para n grande. El uso de n = 1000 es más que suficiente para obtener toda la probabilidad a 16 dígitos significativos en la absorción de los estados, con el resultado de la $s P^{1000} = $ ceros para los estados 1,2,3,4,5,6, y 0.538461538461539 para el estado de 2a, y 0.461538461538462 para el estado 6a. De modo que la probabilidad de obtener consecutivos 1,2 sin que antes de llegar consecutivos 6,6 es 0.538461538461539.
Usted podría intuitivamente creo que la respuesta debe ser de 0,5, pero que está mal. De hecho, es una 50 50 proposición entre llegar a 2a vs 6a en la 1ª transición. Pero a partir de la 2ª transición, las cosas comienzan a moverse en favor de la 2a. Eso es porque si la cadena está en el estado 1 y no directamente de la transición a 2a, todavía se puede llegar a 2a en dos pasos (por ir a 1 y 2a). Pero si no se puede ir directamente desde 6 a 6a, se requiere al menos 3 pasos para llegar a 6a, porque primero debe ir a uno de los estados miembros 1 a 5 y, a continuación, sólo se puede hacer a 6a en 2 pasos más después de que (6, 6a).
Aquí están, en orden de, $P^2$, $P^3$, $P^4$, que muestra 2a ganando una creciente ventaja sobre 6a.
0.1389 0.1111 0.1389 0.1389 0.1389 0.1111 0.1944 0.0278
0.1667 0.1389 0.1667 0.1667 0.1667 0.1389 0.0278 0.0278
0.1667 0.1389 0.1667 0.1667 0.1667 0.1389 0.0278 0.0278
0.1667 0.1389 0.1667 0.1667 0.1667 0.1389 0.0278 0.0278
0.1667 0.1389 0.1667 0.1667 0.1667 0.1389 0.0278 0.0278
0.1389 0.1111 0.1389 0.1389 0.1389 0.1389 0.0278 0.1667
0 0 0 0 0 0 1.0000 0
0 0 0 0 0 0 0 1.0000
0.1296 0.1065 0.1296 0.1296 0.1296 0.1111 0.2176 0.0463
0.1574 0.1296 0.1574 0.1574 0.1574 0.1343 0.0556 0.0509
0.1574 0.1296 0.1574 0.1574 0.1574 0.1343 0.0556 0.0509
0.1574 0.1296 0.1574 0.1574 0.1574 0.1343 0.0556 0.0509
0.1574 0.1296 0.1574 0.1574 0.1574 0.1343 0.0556 0.0509
0.1343 0.1111 0.1343 0.1343 0.1343 0.1111 0.0509 0.1898
0 0 0 0 0 0 1.0000 0
0 0 0 0 0 0 0 1.0000
0.1227 0.1011 0.1227 0.1227 0.1227 0.1042 0.2392 0.0648
0.1489 0.1227 0.1489 0.1489 0.1489 0.1265 0.0818 0.0733
0.1489 0.1227 0.1489 0.1489 0.1489 0.1265 0.0818 0.0733
0.1489 0.1227 0.1489 0.1489 0.1489 0.1265 0.0818 0.0733
0.1489 0.1227 0.1489 0.1489 0.1489 0.1265 0.0818 0.0733
0.1265 0.1042 0.1265 0.1265 0.1265 0.1080 0.0733 0.2083
0 0 0 0 0 0 1.0000 0
0 0 0 0 0 0 0 1.0000
Esto puede ser visto en términos de la línea de fondo para 2a vs 6a a través de la progresión de la $s P^n$, en el que se muestra en el siguiente orden para n = 1,2,3,4.
0.1667 0.1389 0.1667 0.1667 0.1667 0.1389 0.0278 0.0278
0.1574 0.1296 0.1574 0.1574 0.1574 0.1343 0.0556 0.0509
0.1489 0.1227 0.1489 0.1489 0.1489 0.1265 0.0818 0.0733
0.1408 0.1160 0.1408 0.1408 0.1408 0.1197 0.1066 0.0944
Tenga en cuenta que el número de estados puede ser reducido por 2 por el colapso de los estados 3,4,5 en un solo estado, con los cambios pertinentes para P y el vector de estado inicial s.
Edit: De hecho, el número de estados puede ser reducida por 3, para un total de 5, por el colapso de los estados de la 2 a la 5 en un solo estado, que voy a llamar "c". Así que los estados son, en orden, 1,c,6,2,6a. El correspondiente estado de la matriz de transición es
0.1667 0.5000 0.1667 0.1667 0
0.1667 0.6667 0.1667 0 0
0.1667 0.6667 0 0 0.1667
0 0 0 1.0000 0
0 0 0 0 1.0000
con estado inicial = [1/6 2/3 1/6 0 0].
Y, ta dah, para cualquier número de pasos, la absorción de las probabilidades de 2a y 6a coincidir exactamente a la anterior formulación, como se debe, así que no muestran los resultados de nuevo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
