Cadenas de markov

Vista previa del material en texto

Tema 8 – Cadenas de Markov
Proceso estocástico. Cadena de Markov. Probabilidades 
de transición de n etapas. Clasificación de estados. 
Probabilidades de estado estable y tiempos medios. 
Cadenas absorbentes. Campo de aplicación del 
problema de decisión de Markov
INVESTIGACION OPERATIVA
Proceso estocástico
Es un modelo matemático que describe el comportamiento de
un sistema dinámico, sometido a un fenómeno de naturaleza
aleatoria. Es un proceso sin memoria
El sistema evoluciona según un parámetro que normalmente es
el tiempo t, cambiando probabilísticamente de estado
X(t): variable que representa una característica mensurable de
los distintos estados que puede tomar el sistema y su
correspondiente probabilidad de estado.
Procesos sin memoria tipo Markov
La probabilidad de que un sistema se encuentre en un estado 
cualquiera xt+Δt, se puede calcular si se conoce xt
}X(t) / xt)} tP{X( ttt x==+ +
2
Clasificación de los procesos de Markov
Cadenas de Markov
La probabilidad condicional de transición
Cadena de Markov Homogénea: cuando la probabilidad condicional de 
transición del estado i al j en cualquier instante depende de Δt
Naturaleza de X(t)
Discreta Continua
Naturaleza 
del tiempo
Discreto 
(t = 0,1,2,…n)
Cadena de 
Markov de 
p.discreto
Proceso de 
Markov de 
p. discreto
Continuo
(t ≥ 0)
Cadena de 
Markov de 
p. continuo
Proceso de 
Markov de 
p. continuo
 0t , t)(p t)t t,(p ijij =+
3
 t) t(t,pi} / x(t)j t) tP{x( ij +===+
Cadenas de Markov Homogéneas de parámetro discreto 
En una cadena de Markov de parámetro discreto, la probabilidad de 
transición, es la probabilidad de que el sistema se encuentre en un 
estado j en t+ ∆t, habiéndose encontrado en i, en el instante t
Probabilidad condicional de transición
Donde:
t=0, 1, 2, …, discreto
∆t=n=1, 2, …
i=0, 1, …, m
j=0, 1, …, m
∆t = n = número de pasos o transiciones
 i}X(t) / jt)p{X(t t)(pij ==+=
4
MATRIZ DE TRANSICIÓN:
Una matriz de transición para una cadena de Markov de n estados, es una 
matriz de n x n (cuadrada) y con la propiedad adicional de que la suma de los 
registros de cada fila es 1.
Por ejemplo:
PROPIEDADES:
1- la suma de las probabilidades de los estados debe ser igual a 1.
2- la matriz de transición debe ser cuadrada.
3- las probabilidades de transición deben estar entre 0 y 1
Matriz de probabilidades de transición
Probabilidad de pasar de un estado de i a j en un paso
Donde:
Probabilidad de transición de un paso
Probabilidad de transición de dos pasos

















=
)t(p...)t(p)t(p
)t(p...)t(p)t(p
)t(p...)t(p)t(p
m
1
0
P
m ... 1 0 j\i 
mmm1m0
1m1110
0m0100

... 3, 2, 1,nt m ..., 1, 0,i 1)t(p
ij 1)t(p0
m
0j
ij
ij
====


=
6
i} / x(t)j1) x(tppij ==+=
i} / x(t)j2) x(tp{)2(pij ==+=
Mediante Ecuación Chapman - Kolmogorov
Condición Necesaria para que una cadena sea markoviana
Generalizando
2
m
0k
 kjikij
PP(1)P(1)P(2) 
m ..., 0,j m ..., 0,i pp)2(p
==
===
=
n
2
m
0k
kjik
m
0k
kjik
ij
P... 
3)-PP(nP2)-P(n P P 1)-P(n P P(n)
1)p-(np ó )1-n(pp 
i} / x(t)jn){x(t(n)p
==
===
=
==+=

==
p
7
Probabilidad incondicional de estado 
Es la probabilidad de que el sistema se encuentre en el estado i en el 
instante t
El conjunto de probabilidades incondicionales de estado pi(t), 
definen : Vector de probabilidades de estado , p (t)
Probabilidad de estado inicial: es un caso particular para t=0
..m. 2, 1, 0,i ... 2, 1, 0, t)t(p)t(p ixi === =
( )
 1)t(p
 1)t(p0
)t(p...)t(p)t(pp(t)
m
0i
i
i
m10
=

=

=
8
( ) )0(p...)0(p)0(pp(0)
 inicial estado de adprobabilid de vector eldefinen 
(0) pi inicial estado de adesprobabilid de conjunto El
)0(p(0)p
m10
xi
=
== = ti
Probabilidad de estado luego de un paso
En forma análoga se define:
Esta probabilidad se puede expresar en función de las 
probabilidades de estado iniciales aplicando el teorema de la 
probabilidad total 
Quedando expresada la :
Ecuación de Estado
9
mjcon ,...,1,0 )1(p(1)p jxj == =
( )
(t)p paso de luego estado de nalesincondicio 
adesprobabilid de conjunto ; )1(p...)1(p)1(pp(1)
 :es pasoun de luego estado de adprobabilid de vector el
 p (0)p)1(p
i
m10
ij
m
0i
ij
=
=
=
Aplicando ecuación de estado
Ejemplo
estado inicial 
po (0) = 0.5
p1 (0) = 0.5
( )
( )
n
mnm1m0
0n0100
m10
P(0)P (n) 
.P 1-nP 
P(n) . (0)
(n)
P )0((1)
ppp
ppp
 )0(p...)0(p)0(pp(1)
=






=
=














=
p
p
p
pp




10
( )
( ) 0.759) 24.0(
0.778 0.22
0.667 0.33
 5.0 5.0).0( (2) p
)722.0 278.0(
0.667 0.33
1 0
 5.0 5.0).0( (1) p
0.667 0.33
1 0
 P
=





==
=





==






=
PPp
Pp
Es decir la probabilidad de estar en n, se puede 
calcular como la probabilidad de estado inicial 
multiplicada por elevada a la n
11
Clasificación de las cadenas de Markov
Estado accesible y comunicante
• j es accesible desde i, si para algún n1 es pij (n)0 i → j
Es una propiedad Transitiva i → j y j → k  i → k
• Dos estados i y j son comunicantes si j es accesible desde i , y viceversa:
i → j y j → i  i  j
Clases comunicantes y estados sin retorno
Clase comunicante: conjunto de estados que se comunican todos entre sí. 
Puede consistir de un solo estado.
Clasificación:
a) Recurrentes: pij ()>0, la prob de que se encuentre en dicho estado 
después de  transiciones es positiva
Caso especial: estado absorbente pii =1
b) Transitorias: pij ()=0 ; la prob de que se encuentre en dicho estado 
después de  transiciones es nula
Estados sin retorno: no se comunican con ningún otro estado, ni siquiera 
consigo mismo.
Una vez que la cadena ha alcanzado dicho estado la probabilidad de que 
retorne a él es nula 
Ergódicas: todos sus estados se comunican.
a) Regulares: Pn , matriz con todos los
elementos no nulos, cuando todos los
estados pueden comunicarse, en una
cantidad r de pasos.
b) Periódicas: no existe n / Pn tenga todos
sus elementos no nulos
No Ergódicas: no todos sus estados se
comunican.
a) Absorbentes, no se pueden abandonar
b) Cíclicas, pasa cíclicamente según cierto
parámetro de comportamiento
12
Clasificación de las Cadenas de Markov homogeneas en Ergódicas y No 
Ergódicas
Comportamiento de las Cadenas Ergódicas en el 
Régimen Permanente
Régimen Permanente o Estado Estacionario: condición de 
equilibrio estocástico p(estado): estables en el tiempo. En el 
cual no depende de j (estado final) sino solo de i (estado inicial)
Cadenas regulares:
 P(n)limp(0).p(n)lim 
ppp
ppp
ppp
PlimP(n)lim
mj0
mj0
mj0
n
==
==
→→
→
nn
n





13
Todas las filas son 
iguales, no depende 
del estado inicial , 
solo del final
…
…
…
…
…
…
…
Como p(n) = p(n-1).P, y a largo plazo:
p(n)= p(n-1) 
∴ p(n) = p(n).P
y 
 )0(p)0(p)0(p (n) plim 
 
ppp
ppp
ppp
 )0(p)0(p)0(p
m00
mj0
mj0
mj0
mj0







==
=
→
p
n
 1p
m
0j
j
=
=
14
 1p
m
0j
j
=
=
…
…
… …
…
…
… …
… …
Ejemplo
Existen 3 operadores principales de telefonía móvil como lo son Tigo, Comcel y 
Movistar , a los cuales definimos como estados.
Los porcentajes actuales que tiene cada operador en el mercado actual son para
Tigo 0.4 para Comcel 0.25 y para movistar 0.35. (Composición del mercado
actual: estado inicial)
Se tiene la siguiente información un usuario actualmente de Tigo tiene una 
probabilidad de permanecer en Tigo de 0.60, de pasar a Comcel 0.2 y de 
pasarse a movistar de 0.2; si en la actualidad el usuario es cliente de Comcel 
tiene una probabilidad de mantenerse en Comcel del 0.5 de que esta persona se 
cambie a Tigo 0.3 y que se pase a Movistarde 0.2; si el usuario es cliente en la 
actualidad de Movistar la probabilidad que permanezca en movistar es de 0.4 de 
que se cambie a Tigo de 0.3 y a Comcel de 0.3.
Partiendo de esta información podemos elaborar la matriz de transición.
Po = (0.4 0.25 0.35) →estado inicial
Ahora procedemos a encontrar los estados en los siguientes pasos o tiempos, 
esto se realiza multiplicando la matriz de transición por el estado inicial y asi
sucesivamente pero multiplicando por el estado inmediatamente anterior.
Como podemos ver la variación en el periodo 4 al 5 es muy mínima casi 
insignificante podemos decir que ya se a llegado al vector o estado estable.
Almacenes éxito, Carrefour y Sao han investigado la fidelidad de sus clientes y 
han encontrado los siguientes datos:
E1: Exito
E2: Carrefour
E3: Sao
Hallar el estado estable (L)
Estudio del comportamiento de las Cadenas No Ergódicas
Absorbentes
Una cadena absorbente es una cadena no ergodica separable en :
• Uno o varios estados absorbentes
• Uno o varios estados no absorbentes
El estado 1 y 3 son absorbentes 1000
00
0010
00
 
3
2
1
0
P
3 2 1 0Est 
4
3
4
1
2
1
2
1
=
18
1 320
½
½
¼
¾
1
1
Interesa conocer:
a) Número esperado de veces que el proceso pasa por cada estado no 
absorbente antes de ser absorbido.
b) Número esperado de transiciones que el proceso tarda en ser 
absorbido.
c) Probabilidad de absorción de cada estado absorbente
Se reagrupa la matriz:
I (axa):p (permanecer en un estado absorbente en un paso) 
0 (axn):p (pasar de estado absorbente a no absorbente en un paso)
A (nxa): p (absorción en un paso)
N(nxn): p( de no absorción en un paso)
19
 estados 
 
estados 
NA
OI
 P
na
n
a
= a : estados absorbentes
n: estados no absolventes
a) Número esperado de veces que el proceso pasa por cada 
estado no absorbente antes de ser absorbido.
Siendo i y j dos estados no absorbentes
n j / i = 1x I+ IN + IN
2 +…+INn = I / (I-N)= (I-N)-1
00
00
0010
0001
 
2
0
3
1
P
2 0 3 1Est 
4
1
4
3
2
1
2
1
=
7
8
7
2
7
4
7
8
1- 
2
0
 N)-(I
 2 0Est 
=
20
b) Número esperado de transiciones que el proceso tarda en ser 
absorbido.
c) Probabilidad de absorción de cada estado absorbente
Siendo i: estado no absorbente y j: estado absorbente
p(i→j) = IxA + NA + N2A +…=(I+N+N2+…)A= (I-N)-1 A
 
1
1
 N 
1
1
1
1
 N)-(InN 
7
10
7
12
7
8
7
2
7
4
7
8
i
1-
ii =====

2
0
 
0
0
 j)p(i
3 1 
7
6
7
1
7
3
7
4
4
3
2
1
7
8
7
2
7
4
7
8
==→
21
Ejemplo
La empresa jurídica , emplea 3 tipos de abogados: subalternos, superiores y socios. 
Durante cierto año el 10% de los subalternos ascienden a superiores y a un 10% se les 
pide que abandonen la empresa. Durante un año cualquiera un 5% de los superiores 
ascienden a socios y a un 13% se les pide la renuncia. Los abogados subalternos 
deben ascender a superiores antes de llegar a socios. Los abogados que no se 
desempeñan adecuadamente, jamás descienden de categoría.
a) Forme la matriz de transición T
b) Determine si T es regular, absorbente o ninguna de las 2.
c) Calcule la probabilidad de que un abogado subalterno llegue a socio
d) ¿Cuánto tiempo deberá permanecer en su categoría un abogado 
subalterno recién contratado?
e) ¿Cuánto tiempo deberá permanecer en la empresa un abogado 
subalterno recién contratado?
f) Calcule la probabilidad de que un abogado superior llegue a socio.
a) Matriz Transición:
Ahora se procede a restar la matriz normal de la identidad y se halla la 
inversa para ver los tiempos entre estados, para posteriormente esta última 
ser multiplicada por la matriz absorbente y saber las probabilidades de 
cambios de estado.
c) Al multiplicar la matriz inversa por la 
Absorbente se puede hallar dicha 
probabilidad, esta es 0.14
d) Al simplemente hallar la matriz inversa se 
es posible hallar el tiempo en años que 
debería permanecer normalmente un 
abogado subalterno en su compañía, serían 
5 años.
e) Cuando el tiempo debería permanecer un 
abogado subalterno en la empresa?; sería 
sumar el tiempo en que se queda como 
subalterno con el tiempo en que permanece 
como superior: esto es, 5+2.77= 7.77 años.
f) Por último la probabilidad de que pase de 
superior pase a socio es 0,28.
Ejemplo: Almacenes Generales Parts vende partes de automóviles y camiones a 
empresas que cuentan con flotas de vehículos. Cuando una empresa compra, le 
dan 3 meses para pagar, si las cuentas no se saldan en ese período, Almacenes 
cancela la cuenta, la remite a una agencia de cobranzas y da por terminada las 
transacciones. Por lo tanto, clasifica sus cuentas en Nuevas, 1 mes de atraso, 2 
meses de atraso, 3 meses de atraso, Pagadas e Incobrables.
La empresa estudió sus antiguos registros y descubrió que:
70% de las cuentas nuevas se pagan en un mes
60% de las cuentas con 1 mes de retraso se liquidan al final del mes.
50% de las cuentas con 2 meses de atraso se pagan al final de ese último mes.
60% de las cuentas con 3 meses de retraso se remiten a una agencia de 
cobranza.
La matriz de transición del proceso es:
1. Restar una Matriz Identidad menos la Matriz No Absorbente : I-N
Nueva 1 mes R 2 mes R 3 mes R
Nueva 1 -0.3 0 0
1 mes R 0 1 -0.4 0
2 mes R 0 0 1 -0.5
3 mes R 0 0 0 1
2. Hallar la inversa de la Matriz, para hallar la Matriz Fundamental: (I-N)-1
3. Multiplicar la Matriz Inversa por la Matriz Absorbente para obtener las 
probabilidades: (I-N)-1A
El tiempo promedio que debe esperar el Almacén para liquidar sus cuentas se 
halla sumando las filas de la matriz correspondientes a la categoría deseada.
Incobrable Pagado
Nueva 0.036 0.964
1 mes R 0.12 0.88
2 mes R 0.3 0.7
3 mes R 0.6 0.4
Nueva 1 mes R 2 mes R 3 mes R
Nueva 1 0.3 0.12 0.06 1 1.48
1 mes R 0 1 0.4 0.2 1 1.6
2 mes R 0 0 1 0.5 1 1.5
3 mes R 0 0 0 1 1 1
• Ejemplo
La Universidad Libre a estudiado la trayectoria de sus estudiantes y a descubierto que:
A) 70% de los estudiantes de nuevo ingreso regresan al año siguiente, de segundo año el 
15% volverá como estudiante de nuevo ingreso y el resto no regresara.
B) El 75% de los estudiantes de segundo año volverán al año siguiente como estudiantes de 
tercer año, el 15% volverán como estudiantes de segundo año y el resto no regresara.
C) El 80% de los estudiantes de tercer año regresaran al año siguiente como estudiantes de 
último año, 10% volverá como estudiante de tercer año y el resto no regresara.
D) El 85% de los estudiantes de ultimo año se graduaran, y el 10% volverá como estudiante 
de ultimo año y el resto no regresara.
• Nota: Supongamos que la U no permite que un estudiante que se ha dado de baja, vuelva 
y tampoco permite que se cambie de curso a mitad de curso. 
1) Escriba la matriz de transición de estos datos.
Cadenas de Markov de Parámetro Continuo
Análogamente a las cadenas de Markov de parámetro discreto, 
pero ahora es X(t) con t0
pij(∆t)=p{ x(t+ ∆t)=j / x(t)=i } con t0 y ∆t 0 
Tasas o intensidades de transición 
m ..., 1,i ij dd 
donde
ddd
ddd
 D
 )(pd
m
1j
ijii
mmm1m0
0m0100
0ijij
=−=














=








=

=
=




t
t
td
d
28
…
…
…
…
…
…
…
…
Además
Probabilidad incondicional de estado
29
( )
 1)t(p 
 1)t(p0 
Siendo
)t(p...)t(p)t(pp(t)
estado. de adprobabilid m ..., 1, 0,i )t(p)t(p
m
0j
j
j
m10
ixj
=

=
==

=
=
Estudio de las Cadenas en el Régimen Permanente
Derivando respecto a ∆t en ∆t =0
mj0
mmm0
0m00
mi0 ppp 
)t(p...)t(p
)t(p...)t(p
 ppp 


 =



30
0000 
ddd
d
ddd
 ppp
mmmjm0
i0
0m0j00
mi0 




 =
P D 0x =
…
… …
…
…
……
…
…
… …
… …
…
Además:
y dii= -
p = B x A-1
31
 1000 
1ddd
1ddd
1dddpppp
 d- dy 1 
1
1
1
 ppp
1-m mm1m0
1-m 11110
1-m 01 000
m1-m10
i j 
j ii imi0









=
== 

P A Bx
=

 i j 
j id
… …
…
…
…
…
…
…
…
…
…1
1
…