Cadenas de Markov
Cadenas de Markov
Cadenas de Markov
OPERATIVA II
CADENAS DE MARKOV
INTRODUCCION
Las cadenas de Markov son modelos probabilísticos que se usan para predecir
la evolución y el comportamiento a corto y a largo plazo de determinados
sistemas.
Ejemplos:
Pij = Pr{ Xn+1=j / X0=i0, X1=i1, …Xn-1= in-1, Xn=i} = Pr{ Xn+1 = j / Xn = i}
Por tanto:
Pij = Pr{ Xn+1=j / Xn=i } para todo n=0, 1, ……….
Mañana lloverá( estado j), dado que hoy está nublado (estado i).
Mañana cortarán la energía eléctrica en el sector dado que hoy
derribaron un poste en el sector.
La máquina MM3 mañana estará detenida dado que hoy falló.
EJEMPLO:
Consideremos que en un locutorio telefónico con 3 líneas de teléfono, en un instante de
tiempo dado, puede haber un número cualquiera de las líneas ocupadas. Durante un
período de tiempo se observan las líneas telefónicas a intervalos de 2 minutos y se anota
el número de líneas ocupadas en cada instante.
-Sea Xo la v.a. que representa el número de líneas ocupadas al principio del período.
-SeaX1 la v.a. que representa el número de líneas ocupadas cuando se observa en el
segundo instante de tiempo, 2 minutos más tarde.
-En general Xn es una v.a. que representa el número de líneas ocupadas cuando se
observan en el instante de tiempo n-ésimo.
El estado del proceso en cualquier instante de tiempo es el número de líneas que están
siendo utilizadas en ese instante.
Para que este proceso estocástico del número de líneas ocupadas sea
una cadena de Markov es necesario que la probabilidad de cada posible
número de líneas ocupadas en cualquier instante de tiempo dependa
solamente del número de líneas ocupadas 2 minutos antes.
DEFINICIONES BÁSICAS
Propiedad de estacionalidad
La probabilidad del estado futuro depende del valor del estado presente,
pero no de la etapa en que nos encontramos, es decir, no depende de n.
Definición 5:
Tiempo n+1
Consideremos una sucesión de elecciones políticas en un país, si sólo hay dos partidos
políticos fuertes, llamados A y B, los que por lo regular controlan el gobierno, entonces
podemos decir que el país se encuentra en el estado A ó B, si el partido A o B ganara la
elección. Supongamos que las probabilidades 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,
podríamos tener las probabilidades siguientes:
•Siel partido A está en el poder, existe una probabilidad de ¼ que el partido A gane la
próxima elección y una probabilidad de ¾ de que el partido B gane la elección siguiente.
•Si el partido B está en el poder, hay una probabilidad de 1/3 que el partido A gane la
elección siguiente y una probabilidad de 2/3 que el partido B permanezca en el poder.
Solución:
Definimos la variable: Xn= Estado del clima
b) El diagrama de transición:
Solución.
0,5
Sean los siguientes estados:
0,5
(0) = Buen Día 1 0,25
0,5
(1) = Día con lluvia 0,25 0,25
(2) = Día con nieve
0 0,25 2
0,5
b) Determinar la matriz de transición del Proceso
0 1 2
0
Pij = 1 P12
2
Conocer las
probabilidades
Construir la matriz de
una etapa. a
1-a
0 1
No 1- b
llueve
Construir el diagrama llueve
b
Ejercicio. Dibuje los grafos para las matrices siguientes
EJERCICIO:
Construya la matriz de probabilidades.
EJERCICIO:
Construya la matriz de probabilidades. Solución
Probabilidades de transición en n etapas
Se trata de encontrar
i
k
Etapa m
Etapa m+r
j
Etapa m+n
Propiedades:
El producto de dos matrices de Markov siempre es una matriz
El producto de Markov.
de dos matrices de Markov siempre es
En el ejemplo del tiempo
(n+m) (n) en
(m)la Tierra de OZ, las probabilidades de transición en dos etapas
son: P = P P
El producto
0 1de dos
2 matrices de Markov siempre es una matriz de Mark 0,25 0,38 0,38
0 Pij( 2 ) 0,19 0,44 0,38
Pij = 1
2 0,19 0,38 0,44
EJEMPLO:
Sean D1, D2, …..Dn, las demandas durante la primera, segunda y n-ésima
semana respectivamente. (se supone que las Di son v.a. que tienen una
distribución de probabilidad conocida)
Pij(n) = P{Xn = j / X0 = i }
f j( n ) Pij( n )f i( 0 )
i
f (n)
P (n) T
f (0) f (0) T P n
0 1 2
0,80 0,05 0,15
0
P 1 0,04 0,90 0,06
2 0,06 0,04 0,90
Calcular P3
0,540 0,125 0,335
P 3 0,097 0,741 0,162
0,135 0,106 0,759
Multiplicar f0 * Pn . Interpretar.
Respuestas:
Supongamos que X0=i (un estado fijo). Se quiere estudiar el tiempo que
transcurre hasta que ingresamos al estado j por primera vez (j es un estado fijo)
T(i,j)= tiempo que transcurre para ir del estado i al j por primera vez:
Si k ≠ 1 FK ( i , j ) P
L j
iL FK 1(L, j )
F (i, j ) Pi , j Pil F (l , j )
l j
Tiempo Medio
E (T (i, j )) kFK (i, j )
K 1
Ejercicio:
¿ ?
Solución ejercicio:
3
F3 (1,2) PiL * F2 (L,2)
L 1
L2
F3 (1,2) P11 * (P11 * F1 (1,2) P13 * F1 (3,2)) P13 * (P31 * F1 (1,2) P33 * F1 (3,2))
F3 (1,2) P11 * (P11 * P12 P13 * P32 ) P13 * (P31 * P12 P33 * P32 )
F3 (1,2) P11 * P11 * P12 P11 * P13 * P32 P13 * P31 * P12 P13 * P33 * P32 )
Clasificación de estados en una cadena de Markov
Definición 6:
Se dice que el estado j es accesible desde el estado i, si Pij(n)>0 para alguna etapa
n≥0
Que el estado j sea accesible desde el estado i significa que es posible que el
sistema llegue eventualmente al estado j si comienza en el estado i.
En general, una condición suficiente para todos los estados sean accesibles es
que exista un valor de n para el que Pij(n)>0 para todo i y j
Ejemplo:
1 0 0 0
El estado 2 no es accesible desde el estado 3 1 p 0 p 0
El estado 3 si es accesible desde el estado 2
0 1 p 0 p
0 0 0 1
Definición:
Propiedades de la comunicación
i j j k
i k
Si j es accesible desde i, entonces existe n tal que Pij(n)>0
Si k es accesible desde j, entonces existe n tal que Pjk(n)>0
Por tanto solo hay una clase con los estados i, j y k. (por la propiedad de
transitividad)
Definición 7: Una matriz de una sola clase se dice irreducible.
Ejemplo:
1 / 2 1 / 2 0
P 1 / 2 1 / 4 1 / 4 solo hay una clase
0 1 / 3 2 / 3
1 / 2 1 / 2 0 0
1 / 2 1 / 2 0 0
P hay tres clases
1 / 4 1 / 4 1 / 4 1 / 4
0 0 0 1
1
3
Estado (0) = Estado Recurrente (Absorbente): porque una vez que el proceso
entra al estado nunca saldrá de él. (Fii=1)
Estado (1) = Estado Transitorio: porque una vez que el proceso se encuentra en
el estado 1, existe una probabilidad que nunca podrá regresar. (Fii=0)
Estado (2) y (3) = Estados Recurrentes: Una vez que se sale de él, existe
certeza de volver alguna vez. (Fii=1)
Propiedades:
Todos los estados de una cadena de Markov de estado finito irreducible son
recurrentes.
Por tanto:
Clase Transitoria
Clase Recurrente
Clase Recurrente
(Absorbente)
1
3
0
2
Definición 9: PERIOCIDAD DE UN ESTADO:
Un estado se dice que tiene período d para un valor entero mayor que uno y que
cumpla con lo siguiente:
3
0
2
Periodicidad
Ejemplo: En la siguiente CM todos los estados
son periódicos de periodo d=2:
…
0 1 2 3
…
En la siguiente CM todos los estados son periódicos de
periodo d=3:
0 3
1 2 4
Ejemplos
0
La siguiente CM es irreducible,
aperiódica, y por lo tanto
ergódica. 1 2
1 2
CM no es irreducible, y por tanto no es de
ninguno de los demás tipos. Ningún estado
es periódico. 4 es transitorio, y el resto
recurrentes. 1 es absorbente.
4 3
Evolución del proceso en el largo plazo
Definición 10: Para una cadena de Markov irreducible ergódica si el lim Pij( n )
n
existe y es independiente del estado inicial i entonces tiene una distribución
estacionaria π tal que:
1
lim P (n)
ij j 0
n E (T ( j , j ))
donde:
M
j i Pij j=0,1,2……M
i 0
j 0
j 1
Las πj se llaman probabilidades de estado estable de la cadena de Markov
y son iguales al inverso del tiempo esperado de recurrencia.
[T ] * P
i 1
i 0 P11 P12 ... P1n
P P22 ... P2 n
( 1 , 2 ,...... n ) ( 1 , 2 ,... n ) 21
Pn1 Pn 2 Pnn
Ejemplo 1:
Sea:
П = [ П1 П2 П3] , П T=
El sistema a resolver es:
i 1
[T ] * P
= [ π1,π 2,π 3] *
Resolviendo el sistema:
Ejemplo 2:
i 1 0 1 2 3 1
0 0.080 0.184 0.368 0.368
0.632 0.368 0.00 0.00
[T ] * P 1*
2 0.264 0.368 0.368 0.00
3 0.080 0.184 0.368 0.368
El costo promedio esperado por unidad de tiempo (a la larga), está dado por:
1 n
j C ( j) = lim E C ( X i )
j 0
n
n i 1
Ejemplo 1:
0 si X1 = 0
C (xi) 2 si X1 = 1
=
8 si X1 = 2
18 si X1 = 3
El costo promedio esperado por semana, a la larga, por mantener el inventario,
se puede obtener de la ecuación:
1 n
lim E C ( X i ) = 0(0.285) + 2(0.285) + 8(0.264) + 18(0.166) = 5.67
n
n i 1
Ejemplo 2:
0 ,1 0 ,8 0 ,1
0 0 ,5 0 ,5
P
1 0 0
a) ¿Cuál será el costo de mantenimiento correctivo de los camiones ( filtro
obstruido)?
Solución:
• 0 =
0,286
•1= 0,457
•2= 0,257….25,7% de las veces filtro del camión estará obstruido.
Solución:
•En este caso tendremos cambios en la matriz original ya que el cambio de
estado será de parcialmente obstruido a limpio.
j 0
j C ( j)
Estados absorbentes
El estado k se llama estado absorbente si Pkk=1, de manera que una vez que la
cadena llega al estado k, permanece ahí para siempre.
Considere una tienda que clasifica el saldo de un cliente como pagado (estado
0), 1 a 30 días de retraso (estado 1), 31 a 60 días de retraso (estado 2) o mala
deuda (estado 3). Las cuentas se revisan mensualmente. Se entregan datos
históricos de la tienda y se obtiene la siguiente matriz de transición:
0.2
1 0 0 0 0.7 1
0.7 0.2 0.1 0 0.1 0.2
P 1
0.5 0.1 0.2 0.2 0 0.1 2 3
0 0 0 1 0.5
0.2 1
En este caso, los estados absorbentes son los estados (0) y (3). La tienda se
interesa en determinar la probabilidad de que un cliente llegue a ser mala deuda
dado que actualmente es deudor (estado 1 o estado 2).
Re solviendo :
F (1,3) 8 * F (2,3) 2
F (1,3) 0.125 * F (2,3) Entonces, aproximadamente el 3% de
los clientes que deben entre 1 a 30 días
acaban siendo malos deudores,
8 * F (2,3) 2 0.125 * F (2,3) mientras que el 25% de los clientes que
F (2,3) * (8 0.125 ) 2 deben entre 31 a 60 días llegan a la
2 misma categoría.
F (2,3)
8 0.125
F (2,3) 0,254
F (1,3) 0,032