CAD 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
Se cumple que:
La probabilidad de que el sistema se encuentre en un estado cualquiera x t+Δten el instante t+Δt , se puede calcular si se conoce el estado inmediatamente anterior x t, independiente de los estados anteriores
2
Clasificación de los procesos de Markov
Cadenas de Markov homogéneas 
La probabilidad condicional de transición se expresa:
Cadena de Markov Homogénea: cuando la probabilidad condicional de transición del estado i al j en cualquier instante t, solo 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
3
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 = entero se denomina número de pasos o transiciones 
4
Matriz de probabilidades de transición
El conjunto de probabilidades de transición pij, definen la matriz de probabilidades de transición
Probabilidad de pasar de un estado de i a j en un paso
Donde se cumplen :
Probabilidad de transición de 1 paso
Probabilidad de transición de 2 pasos
5
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
Ecuación Chapman - Kolmogorov
Condición Necesaria pero no suficiente para que una cadena sea Markoviana
En dos pasos
7
Probabilidad incondicional de estado 
En una cadena de Markov homogénea de parámetro discreto, 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
8
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
Aplicando ecuación de estado
Ejemplo
 estado inicial 
po (0) = 0.5
p1 (0) = 0.5
10
Es decir la probabilidad de estar en n, se puede calcular como la probabilidad de estado inicial multiplicada por P 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:
Recurrentes: pij ()>0, la prob de que se encuentre en dicho estado después de  transiciones es positiva
 Caso especial: estado absorbente pii =1
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.
Regulares: Pn , matriz con todos los elementos no nulos, cuando todos los estados pueden comunicarse, en una cantidad r de pasos. Es decir que Pn es una matriz con todos los elementos no nulos.
Periódicas: no existe n / Pn tenga todos sus elementos no nulos, es decir que permite asegurar siempre la presencia de al menos un cero en Pn.
No Ergódicas: no todos sus estados se comunican.
Absorbentes, no se pueden abandonar
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:
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 
14
…
…
…
…
…
…
…
…
…
…
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 Movistar de 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
18
1
3
2
0
½
½
¼
¾
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)
19a : estados absorbentes
n: estados no absolventes
Numero esperado de veces que el proceso pasa por cado estado no absorbente antes de ser absorbido.
Número esperado de veces que la cadena puede pasar por un estado no absorbente j, habiendo comenzado en un estado no absorbente genérico i, esta dado por:
n j / i = 1x I + 1xN + 1xN2 +…+1Nn = I / (I-N) = (I-N)-1
Siendo i y j dos estados no absorbentes
				Si la cadena comienza por el estado 
				no absorbente 0 pasara en promedio
				8/7 veces, incluyendo el comienzo y 
				Por el estado 2 ; 4/7 veces, antes de 
				Absorbidos por los estados 1 y 3
 
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
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.
		Socio 	Renuncie	Subalterno	Superior
	Socio 	1	0	0	0
	Renuncie	0	1	0	0
	Subalterno	0	0,1	0,8	0,1
	Superior	0,05	0,13	0	0,82
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
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.
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 continuo
pij(∆t)=p{ x(t+ ∆t)=j / x(t)=i } con t0 y ∆t 0 
 Tasas o intensidades de transición 
Matriz de 
tasas de
transición D
28
…
…
…
…
…
…
…
…
Además por la Probabilidad incondicional de estado
29
Estudio de las Cadenas en el Régimen Permanente
Derivando respecto a ∆t en ∆t =0
30
P
D
0
x
=
…
…
…
…
…
…
…
…
…
…
…
…
…
…
Además:
 
 
				y dii= - 
 
				 p = B x A-1
31
P
A
B
x
=
…
…
…
…
…
…
…
…
…
…
…
1
1
…
}
X(t)
 / 
 x
t)}
 t
P{X(
t
t
t
x
=
=
D
+
D
+
 
0
t
 
,
 
t)
(
p
 
t)
t
 t,
(
p
ij
ij
³
"
D
=
D
+
 
t)
 t
(t,
p
i}
 
 / x(t)
j
 
t)
 t
P{x(
ij
D
+
=
=
=
D
+
 
i}
X(t)
 / 
j
t)
p{X(t
 
t)
(
p
ij
=
=
D
+
=
D
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
D
D
D
D
D
D
D
D
D
=
)
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
 
mm
m1
m0
1m
11
10
0m
01
00
M
M
M
M
M
...
 
3,
 
2,
 
1,
n
t
 
m
 
...,
 
1,
 
0,
i
 
1
)
t
(
p
ij
 
1
)
t
(
p
0
m
0
j
ij
ij
=
=
D
=
=
D
"
£
D
£
å
=
i}
 / x(t)
j
1)
 x(t
p
p
ij
=
=
+
=
i}
 / x(t)
j
2)
 x(t
p{
)
2
(
p
ij
=
=
+
=
2
m
0
k
 
kj
ik
ij
P
P(1)P(1)
P(2)
 
m
 
...,
 
0,
j
 
m
 
...,
 
0,
i
 
p
p
)
2
(
p
=
=
\
=
=
=
å
=
n
2
m
0
k
kj
ik
m
0
k
kj
ik
ij
ij
P
...
 
 
3)
-
PP(n
P
2)
-
P(n
 
P
 
P
 
1)
-
P(n
 
P
 
P(n)
1)p
-
(n
p
 
 
 
)
1
-
n
(
p
p
 
(n)
p
 
i}
 / x(t)
j
n)
{x(t
(n)
p
=
=
=
=
=
\
=
=
=
+
=
å
å
=
=
p
..m.
 
2,
 
1,
 
0,
i
 
...
 
2,
 
1,
 
0,
 t
)
t
(
p
)
t
(
p
i
x
i
=
=
=
=
(
)
 
1
)
t
(
p
 
1
)
t
(
p
0
)
t
(
p
...
)
t
(
p
)
t
(
p
p(t)
m
0
i
i
i
m
1
0
=
£
£
=
å
=
(
)
 
)
0
(
p
...
)
0
(
p
)
0
(
p
p(0)
 
inicial
 
estado
 
de
 
ad
probabilid
 
de
 vector 
el
definen 
(0)
 
pi
 
inicial
 
estado
 
de
 
ades
probabilid
 
de
 
conjunto
 
El
)
0
(
p
(0)
p
m
1
0
x
i
=
=
=
=
t
i
m
j
con
,...,
1
,
0
 
 
)
1
(
p
(1)
p
j
x
j
=
=
=
(
)
(t)
p
 
paso
 
de
 
luego
 
estado
 
de
 
nales
incondicio
 
ades
probabilid
 
de
 
conjunto
 
;
 
)
1
(
p
...
)
1
(
p
)
1
(
p
p(1)
 
:
es
 
paso
un 
 
de
 
luego
 
estado
 
de
 
ad
probabilid
 
de
 vector 
el
 
p
 
(0)
p
)
1
(
p
i
m
1
0
ij
m
0
i
i
j
=
=
å
=
(
)
(
)
n
mn
m1
m0
0n
01
00
m
1
0
P(0)P
 
(n)
 
.P
 
1
-
n
P
 
P(n)
 
.
 
(0)
(n)
P
 
)
0
(
(1)
p
p
p
p
p
p
 
 
)
0
(
p
...
)
0
(
p
)
0
(
p
p(1)
=
þ
ý
ü
î
í
ì
=
\
=
\
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
=
p
p
p
p
p
K
M
O
M
M
O
M
K
(
)
(
)
0.722)
 
275
.
0
(
0.778
 
0.22
0.667
 
0.33
 
5
.
0
 
5
.
0
).
0
(
 
(2)
 
p
)
8335
.
0
 
167
.
0
(
0.667
 
0.33
1
 
 
0
 
5
.
0
 
5
.
0
).
0
(
 
(1)
 
p
0.667
 
0.33
1
 
 
0
 
 
P
=
÷
÷
ø
ö
ç
ç
è
æ
=
=
=
÷
÷
ø
ö
ç
ç
è
æ
=
=
÷
÷
ø
ö
ç
ç
è
æ
=
PP
p
P
p
 
 
P(n)
lim
p(0).
p(n)
lim
 
p
p
p
p
p
p
p
p
p
P
lim
P(n)
lim
m
j
0
m
j
0
m
j
0
n
=
=
=
=
¥
®
¥
®
¥
®
n
n
n
L
L
M
M
M
L
L
M
M
M
L
L
 
 
)
0
(
p
)
0
(
p
)
0
(
p
 
(n)
 
p
limp
p
p
p
p
p
p
p
p
 
)
0
(
p
)
0
(
p
)
0
(
p
m
0
0
m
j
0
m
j
0
m
j
0
m
j
0
L
L
L
L
M
M
M
L
L
M
M
M
L
L
L
L
=
=
´
=
¥
®
p
n
 
 
1
p
m
0
j
j
å
=
=
1
0
0
0
0
0
0
0
1
0
0
0
 
3
2
1
0
P
3
 
2
 
1
 
0
Est 
 
4
3
4
1
2
1
2
1
=
 
estados
 
 
estados
 
N
A
O
I
 
P
n
a
n
a
=
0
0
0
0
0
0
1
0
0
0
0
1
 
2
0
3
1
P
2
 
0
 
3
 
1
Est 
 
4
1
4
3
2
1
2
1
=
7
8
7
2
7
4
7
8
1
-
 
2
0
 
N)
-
(I
 
2
 
0
Est 
 
 
=
 
 
 
1
1
 
 
 
N
 
 
 
1
1
1
1
 
 
N)
-
(I
n
N
 
7
10
7
12
7
8
7
2
7
4
7
8
i
1
-
i
i
=
´
=
=
=
=
M
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
=
´
=
®
 
 
 
 
N
A
O
I
 
P
n
a
n
a
=
Nueva1 mes R2 mes R3 mes R
Nueva1-0.300
1 mes R01-0.40
2 mes R001-0.5
3 mes R0001
Incobrable Pagado
Nueva0.0360.964
1 mes R0.120.88
2 mes R0.30.7
3 mes R0.60.4
Nueva1 mes R2 mes R3 mes R
Nueva10.30.120.0611.48
1 mes R010.40.211.6
2 mes R0010.511.5
3 mes R000111
m
 
...,
 
1,
i
 
i
j
 
 
d
d
 
donde
d
d
d
d
d
d
 
D
 
)
(
p
d
m
1
j
ij
ii
mm
m1
m0
0m
01
00
0
ij
ij
=
¹
"
-
=
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
=
÷
ø
ö
ç
è
æ
D
D
=
å
=
=
D
K
M
O
M
M
O
M
K
t
t
t
d
d
(
)
 
1
)
t
(
p
 
 
1
)
t
(
p
0
 
Siendo
)
t
(
p
...
)
t
(
p
)
t
(
p
p(t)
estado.
 
de
 
ad
probabilid
 
m
 
...,
 
1,
 
0,
i
 
)
t
(
p
)
t
(
p
m
0
j
j
j
m
1
0
i
x
j
=
£
£
=
=
=
å
=
=
m
j
0
mm
m0
0m
00
m
i
0
p
p
p
 
 
)
t
(
p
...
)
t
(
p
)
t
(
p
...
)
t
(
p
 
p
p
p
L
L
M
O
M
M
M
L
L
=
D
D
D
D
´
0
0
0
0
 
 
d
d
d
d
d
d
d
 
p
p
p
mm
mj
m0
i0
0m
0j
00
m
i
0
L
L
L
M
M
L
L
L
L
=
´
 
1
0
0
0
 
 
 
 
1
d
d
d
1
d
d
d
1
d
d
d
 
 
p
p
p
p
 
d
-
 
d
y 
 
1
 
1
1
1
 
p
p
p
1
-
m
 
m
m1
m0
1
-
m
 
1
11
10
1
-
m
 
0
1
 
0
00
m
1
-
m
1
0
i
 
 
j
 
j
 
i
i
 
i
m
i
0
L
L
M
O
M
M
M
O
M
L
L
L
M
L
L
=
´
=
=
´
å
¹
"
å
¹
"
i
 
 
j
 
j
 
i
d