valor imperfecta

Instituto de Ciencias y Estudios Superiores de Tamaulipas A.C.











Carrera: Ingeniería en Sistemas Computacionales
Asignatura: Teoría de la Computación
Tema: Cadenas de MARKOV


Unidad III. Cadenas de Markov
Objetivo de la unidad: Formulará problemas de estudio de mercado y de comportamiento de sistemas estocásticos mediante modelos de cadenas de markov.

3.1.-Introducción.
3.2.- Formulación de las cadenas de markov.
3.3. -Procesos estáticos.
3.4.- Propiedad markoviana de primer orden.
3.5.- Probabilidad de transición estacionaria.
3.6.- Probabilidad de transición estacionaria de “N” pasos.
3.7.- Estados absorbentes.
3.8.- Probabilidad de transición estacionaria de estados estables.
3.9.- Tiempos de primer paso.
3.10.- Uso de programas decomputación.

3.1.- Introducción.
Definición de cadena de Markov.
Una cadena de markov es una sucesión de ensayos similares u observaciones en el cual cada ensayo tiene el mismo número finito de resultados posibles y en donde la probabilidad de cada resultado para un ensayo dado depende solo del resultado del ensayo inmediatamente precedente y no de cualquier resultado previo.

Propiedad de Markov
Dadauna secuencia de variables aleatorias: x1, x2, x3,…
xn, es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de xn + 1. En estados pasados es una función de xn por si sola, entonces:

P (xn+1 = xn+1 | xn = xny
xn-1 = xn-1,…x2 = x2
x1 = x1) = P (xn+1 = xn+1 | xn = xn)

Donde y es el estado en el proceso en el instante x; esta identidad es denominadapropiedad de markov: El estado en el tiempo t+1 depende del estado en t y no de la evolución del anterior sistema.

Matriz de transición
Al trabajar con cadenas de markov es útil pensar la sucesión de ensayos como experimentos efectuados en cierto sistema físico.

Ejemplo: existen dos partidos políticos fuertes llamados A y B, que por lo regular controlan al gobierno, entonces podemos decir que elpaís se encuentra en el estado A o B si el partido A o B ganara la elección. Cada ensayo coloca al país en uno de los dos estados (A o B). Una sucesión de 10 elecciones podría producir resultados tales como los siguientes: A, B, A, A, B, B, B, A, B, B.

La primera elección en la sucesión deja en el poder al partido A, la segunda fue ganada por el partido B, y así sucesivamente hasta que ladécima elección la gana el partido B. Supongamos que las posibilidades de que el partido A o B ganen la próxima elección son determinadas por completo por el partido que está en el poder ahora. Por ejemplo podríamos tener las probabilidades siguientes.

Si el partido A está en el poder, existe una probabilidad de un ¼ que el partido A ganara la próxima elección y una probabilidad de ¾ de que elpartido B gane la siguiente elección.
Si el partido B está en el poder hay una probabilidad de 1/3 de que el partido A gane la elección siguiente y una probabilidad de 2/3 de que el partido B permanezca en el poder.

En tal caso, la sucesión de elecciones forman una cadena de markov, dado que las probabilidades de los dos resultados de cada elección están determinadas por el resultado de la elecciónpresente.

Diagrama de transiciones







*Las flechas representan la probabilidad de cambiar de un estado a otro.
A B
A 1/4 3/4
B 2/3 1/3
3.3.- Procesos estocásticos
Una sucesión de observaciones x1, x2… se denomina proceso estocástico.

Si los valores de estas observaciones no se pueden predecir exactamente.
Pero se pueden especificar las probabilidadespara los distintos valores posibles en cualquier instante del tiempo.

X1: Valor que define el estado inicial del tiempo.
Xn: Valor que define el estado del proceso en el instante del tiempo n.

Para cada posible valor del estado inicial S1 para cada uno de los sucesivos valores Sn de los estados Xng n = 2,3, especificamos:

P (Xn+1 = Sn+1 | x1 = S1, x2 = s2, … xn = sn)

Una cadena de...