INVESTIGACION DE OPERACIONES II Cadenas de Markov

”

Asignatura: INVESTIGACION DE OPERACIONES II

Tutor: Juan Carlos Lora

Integrantes:

Lugar: Universidad de Cartagena

PROTOCOLO 2:Cadenas de Markov

Cadenas de Markov

Una cadena  de markov es un proceso estocástico que cumple con la propiedad de markov. proceso estocástico quiere decir;  proceso o sucesión de eventos que se desarrolla en el tiempo en el que el resultado en cualquier etapa depende en alguna medida del azar, sirve para tratar magnitudes aleatorias que varían con el tiempo, y la propiedad de markov  que recibe el nombre del matemático ruso Andrei  Andreevitch  Markov se refiere a una sucesión de eventos similares u observaciones en donde cada evento tiene el mismo número finito de resultados posibles, donde la probabilidad de cada resultado en un evento dado depende sólo del resultado del evento inmediatamente anterior y no de cualquier resultado previo, cadena de markov cadena de eventos, cada evento ligado al inmediatamente anterior.

La probabilidad del estado futuro Xn+1   No depende de los estados anteriores X1, . . . , Xn−1, y Solamente depende del estado actual Xn Es decir Para n = 1, 2, . . . y Para cualquier sucesión de estados s1, . . . , sn+1   P (Xn+1 = sn+1 | X1 = s1, X2 = s2, . . . , Xn = sn) = P (Xn+1 = sn+1 | Xn = sn)

Clases de cadenas de markov

Cadenas irreducibles

Una cadena irreducible es aquella en la que todos los estados son alcanzables desde Cualquier otro estado de la cadena en un número finito de pasos. Una cadena de Márkov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí):

1. Desde cualquier estado de E se puede acceder a cualquier otro.
2. Todos los estados se comunican entre sí.
3. C(x)=E para algún x∈E.
4. C(x)=E para todo x∈E.
5. El único conjunto cerrado es el total.

Cadenas positivo-recurrentes

Una cadena de markov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

[pic 1]

Cadenas regulares o ergódicas

Se tenía que todos los estados en una cadena irreducible pertenecen a la misma clase. Si todos los estados son ergódicos, esto es, recurrentes, no nulos y periódicos entonces se define la cadena como ergódica Una cadena de Márkov sedice regular también primitiva o ergódica si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero.  Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que       [pic 2]

Donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector invariante es único

Cadenas absorbentes

Una cadena de Márkov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones la primera es que la cadena tiene al menos un estado absorbente y segunda De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos como resultado que su matriz de transición siempre se puede llevar a una de la forma        [pic 3]

Donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.    [pic 4], esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.

Cadenas periódicas

Si un estado j es periódico con periodo δ y otro estado i comunica con él, entonces el estado i también es periódico con el mismo periodo. De este modo, el periodo es una característica común del conjunto irreducible y cerrado y se puede hablar del periodo de una subcadena irreducible.

Clases de estados

Los estados de una cadena se pueden dividir en dos subconjuntos disjuntos (alguno Puede ser ∅): uno está formado por los estados transitorios y el otro por los recurrentes.

Estado absorbente

Un estado es absorbente cuando una vez que se entra en él no se puede salir del mismo. También llamado estado trampa Un estado Ei es absorbente si

Estado periódico

El periodo de un estado x ∈ E se define como:     [pic 5]donde [pic 6] denota máximo común divisor. Dicho de otra manera un estado x es periódico con periodo k>1 si k es el menor número tal que todas las trayectorias que parten del estado x y regresan al estado x tienen una longitud múltiplo de k.

...