Cadenas de Markov practica

Vista previa del material en texto

Cadenas de Markov
Procesos Estocásticos
Fuente: Rojo, H; Miranda, M. Cadenas de Markov.Investigación Operativa.FIUBA.2016
ENZO CORTE
Máquina de escribir
No importa estados pasados ni presente, es como tirar una moneda
ENZO CORTE
Máquina de escribir
Importa el estado presente
ENZO CORTE
Máquina de escribir
Importa el pasado, por ejemplo para predicciones de venta que debemos tener en cuenta los antecedentes
Clasificación de los procesos estocásticos según la naturaleza continua 
o discreta de las variables
Fuente: Rojo, H; Miranda, M. Cadenas de Markov.Investigación Operativa.FIUBA.2016
ENZO CORTE
Máquina de escribir
Si la vble X(t) toma valores discretos hablamos de cadenas, y si toma valores continuos hablamos de procesos
Las Cadenas de Markov homogéneas, tanto en parámetro discreto como 
continuo, describen una gran cantidad de procesos físico-económicos de la 
realidad, como ser: 
 Análisis de comportamientos de compra y lealtad a una marca 
(“brandswitching”), 
 Estudio de reemplazo de equipos, 
 Planeamiento de necesidades de personal, 
 Análisis de inventarios, 
 Análisis de créditos, 
 Estudio de sistemas de colas, etc. 
Cadenas de Markov Homogéneas de parámetro discreto
Una Cadena es homogénea si para cualquier t las probabilidades de 
transición de i a j solo dependen de Dt
ENZO CORTE
Máquina de escribir
Probabilidad de pasar de un estado i a un estado j en un intervalo delta T
ENZO CORTE
Máquina de escribir
Con los estados armo la matriz
ENZO CORTE
Máquina de escribir
Sumatoria en cada fila
Probabilidad condicional de transición de un paso-Matriz de las probabilidades de 
transición de un paso
ENZO CORTE
Máquina de escribir
Un paso significa que delta T toma el valor de 1, y asi sera sucesivamente
Ejemplo 1:
Suponga que una fábrica de bebidas de cola produce sólo dos tipos. Dado que
una persona la última vez compró cola 1, hay 90% de probabilidades de que sus
siguiente compra sea cola 1.Dado que la última compra de una persona fue cola
2, hay 80 % de probabilidades de que sus siguiente compra sea cola 2.
𝐸𝑠𝑡𝑎𝑑𝑜𝑠
𝐸𝑠𝑡𝑎𝑑𝑜 1: 𝐶𝑜𝑚𝑝𝑟𝑎𝑑𝑜𝑟 𝑐𝑜𝑙𝑎 1
𝐸𝑠𝑡𝑎𝑑𝑜 2: 𝐶𝑜𝑚𝑝𝑟𝑎𝑑𝑜𝑟 𝐶𝑜𝑙𝑎 2 P =
0,9 0,1
0,2 0,8
Cola 1 Cola 2
Cola 1
Cola 2
Marca recién comprada
X Y Z
X 0,3 0,2 0,5
Y 0,1 0,6 0,3
Z 0,4 0,3 0,3
Se efectúa una encuesta de mercado de tres marcas de alimento X, Y
y Z. Cada vez que el cliente compra un nuevo paquete puede comprar de
la misma marca o cambiarse a otra. Se han obtenido los siguientes datos
estimados que se expresan como fracciones decimales:
Ejemplo 2:
𝐸𝑠𝑡𝑎𝑑𝑜𝑠
𝐸𝑠𝑡𝑎𝑑𝑜 1: 𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑋 𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 2: 𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑌 𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 3:𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑍𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
P =
0,3 0,2 0,5
0,1 0,6 0,3
0,4 0,3 0,3
Ecuación de Chapman-Kolmogorov
P ∆𝑡 = 2 = P ∆𝑡 = 1
2
P ∆𝑡 = 𝑛 = P ∆𝑡 = 1
𝑛
P 𝑛 = 𝑃𝑛
Expresión general de la 
ecuación de Chapman-
Kolmogorov
En el Ejemplo 1:…
ENZO CORTE
Máquina de escribir
Probabilidad de que compre cola 1 o 2 luego de n compras
Probabilidad incondicional de estado
Ԧ𝑝 1 = Ԧ𝑝(0)P
Ecuación general de Estado 𝒑 𝐭 + ∆𝒕 = 𝒑(𝐭)𝐏(∆𝒕)
ENZO CORTE
Máquina de escribir
Se refiere a un valor puntual en un determinado tiempo
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. Es decir
que Pn es una matriz con todos los elementos no nulos.
b) 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.
a) Absorbentes, no se pueden abandonar
b) Cíclicas, pasa cíclicamente según cierto parámetro de comportamiento.
ENZO CORTE
Máquina de escribir
No puedo volver a un estado anterior
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





Todas las filas son 
iguales, no depende 
del estado inicial , 
solo del final
ENZO CORTE
Máquina de escribir
Se llega al regimen estacionario
Como p(n) = p(n-1).P, y a largo plazo:
p(n)= p(n-1) 
∴ p(n) = p(n).P
y 1p
m
0j
j


Ejemplo 1:
1.Si una persona en la actualidad es comprador de cola2 ¿Cuál es la
probabilidad de que siempre compre cola 1 dos veces a partir de ahora.
2.Si una persona en la actualidad es comprador de cola 1¿Cuál es la
probabilidad de que compre cola 1 tres ocasiones a partir de ahora?
𝐸𝑠𝑡𝑎𝑑𝑜𝑠
𝐸𝑠𝑡𝑎𝑑𝑜 1: 𝐶𝑜𝑚𝑝𝑟𝑎𝑑𝑜𝑟 𝑐𝑜𝑙𝑎 1
𝐸𝑠𝑡𝑎𝑑𝑜 2: 𝐶𝑜𝑚𝑝𝑟𝑎𝑑𝑜𝑟 𝐶𝑜𝑙𝑎 2 P =
0,9 0,1
0,2 0,8
Cola 1 Cola 2
Cola 1
Cola 2
Cadena Ergódica Regular
Suponga que una fábrica de bebidas de cola produce sólo dos tipos. Dado que
una persona la última vez compró cola 1, hay 90% de probabilidades de que sus
siguiente compra sea cola 1.Dado que la última compra de una persona fue cola
2, hay 80 % de probabilidades de que sus siguiente compra sea cola 2.
1.Si una persona en la actualidad es comprador de cola2 ¿Cuál es la probabilidad
de que siempre compre cola 1 dos veces a partir de ahora.
𝑃2 =
0,83 0,17
0,34 0,66
2.Si una persona en la actualidad es comprador de cola 1¿Cuál es la probabilidad
de que compre cola 1 tres ocasiones a partir de ahora?
La probabilidad de que compre cola 1 siendo comprador de cola 2 es 0,34
𝑃3 =
0,781 0,219
0,438 0,562
Cola 1 Cola 2
Cola 1 Cola 2
Cola 1
Cola 2
Cola 1
Cola 2
Marca recién comprada
X Y Z
X 0,3 0,2 0,5
Y 0,1 0,6 0,3
Z 0,4 0,3 0,3
Se efectúa una encuesta de mercado de tres marcas de alimento X, Y
y Z. Cada vez que el cliente compra un nuevo paquete puede comprar de
la misma marca o cambiarse a otra. Se han obtenido los siguientes datos
estimados que se expresan como fracciones decimales.
a. Plantee el problema, identifique y formule el modelo completo.
b. Se estima en este momento que el 30% de los clientes compran la
marca X, 20% la marca Y y 50% la marca Z. Cuál será la distribución de los
clientes dos periodos de tiempo después?. Interprete los resultados
Ejemplo 2:
𝐸𝑠𝑡𝑎𝑑𝑜𝑠
𝐸𝑠𝑡𝑎𝑑𝑜 1: 𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑋 𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 2: 𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑌 𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 3:𝐶𝑙𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑚𝑝𝑟𝑎 𝑚𝑎𝑟𝑐𝑎 𝑍𝑑𝑒 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
P =
0,3 0,2 0,5
0,1 0,6 0,3
0,4 0,3 0,3
a. Plantee el problema, identifique y formule el modelo completo.
Es una Cadena de Markov homogénea de parámetro discreto ergódica
b. Se estima en este momento que el 30% de los clientes compran la
marca X, 20% la marca Y y 50% la marca Z. Cuál será la distribución de
los clientes dos periodos de tiempo después?. Interprete los resultados
𝑝 2 = 𝑝(0)𝑃2
p(0)=(0,3 0,2 0,5) 𝑃2 =
0,31 0,33 0,36
0,21 0,47 0,32
0,27 0,35 0,38
𝑝 2 = 𝑝(0)𝑃2=(0,27 0,368 0,362)
Cadena No Ergódicas Absorbentes
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)
 estados 
 
estados 
NA
OI
 P
na
n
a

ENZO CORTE
Máquina de escribir
Matrices
ENZO CORTE
Máquina de escribir
Matriz identidad
ENZO CORTE
Máquina de escribir
Matriz nula
ENZO CORTEMáquina de escribir
Matriz de estados absorventes
ENZO CORTE
Máquina de escribir
MAtriz de estados no absorventes
ENZO CORTE
Máquina de escribir
No hay retorno
ENZO CORTE
Máquina de escribir
Lo que me interesa conocer el numero esperado de veces que el proceso pasa por cada estado no absorvente antes de ser absorvido, el numero esperado de transiciones que el proceso tarda en ser absorvido y la probabilidad de absorcion de cada estado absorvente
En la universidad están realizando un estudio para determinar el número promedio de
años que pasa un estudiante en la misma, a partir de la información brindada en la
siguiente tabla de probabilidades de transición:
1.¿Cómo modelaría el problema y por qué? Fundamente su respuesta
Suponiendo que una vez que salga un estudiante ya nunca vuelve a inscribirse
2¿Cuántos años tardará en recibirse un estudiante que ingresa en primer año?
Fundamente la respuesta
3. Del total de 5000 ingresantes del año 2019, cuántos se recibirán?Fundamente la
respuesta
1 año 2 año 3 año 4 año Abandona Se recibe
1 año 0,1 0,8 0 0 0,1 0
2 año 0 0,1 0,85 0 0,05 0
3 año 0 0 0,15 0,8 0,05 0
4 año 0 0 0 0,1 0,05 0,85
Abandona 0 0 0 0 1 0
Se recibe 0 0 0 0 0 1
Ejemplo 3:
ENZO CORTE
Máquina de escribir
Estados
Absorventes
1)El modelo es una Cadena de Markov no ergódica
1 año 2 año 3 año 4 año Abandona Se recibe
1 año 0,1 0,8 0 0 0,1 0
2 año 0 0,1 0,85 0 0,05 0
3 año 0 0 0,15 0,8 0,05 0
4 año 0 0 0 0,1 0,05 0,85
Abandona 0 0 0 0 1 0
Se recibe 0 0 0 0 0 1
𝐸𝑠𝑡𝑎𝑑𝑜𝑠
𝐸𝑠𝑡𝑎𝑑𝑜 1: 𝐴𝑙𝑢𝑚𝑛𝑜 𝑑𝑒 1° 𝑎ñ𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 2: 𝐴𝑙𝑢𝑚𝑛𝑜 𝑑𝑒 2° 𝑎ñ𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 3: 𝐴𝑙𝑢𝑚𝑛𝑜 𝑑𝑒 3° 𝑎ñ𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 4: 𝐴𝑙𝑢𝑚𝑛𝑜 𝑑𝑒 4° 𝑎ñ𝑜
𝐸𝑠𝑡𝑎𝑑𝑜 5:𝐴𝑙𝑢𝑚𝑛𝑜 𝑎𝑏𝑎𝑛𝑑𝑜𝑛𝑎
𝐸𝑠𝑡𝑎𝑑𝑜 6: 𝐴𝑙𝑢𝑚𝑛𝑜 𝑠𝑒 𝑟𝑒𝑐𝑖𝑏𝑒
1.¿Cómo modelaría el problema y por qué? Fundamente su respuesta
Suponiendo que una vez que salga un estudiante ya nunca vuelve a
inscribirse
2¿Cuántos años tardará en recibirse un estudiante que ingresa en primer
año? Fundamente la respuesta
3,96433471 1 año
(I-N)-11= 3,20987654 2 año
2,22222222 3 año
1,11111111 4 año
Cadena de Markov homogénea no ergódica
3. Del total de 5000 ingresantes del año 2019, cuántos se
recibirán?Fundamente la respuesta
Abandona Se recibe
0,25377229 0,74622771 1 año
(I-N)-1A= 0,16049383 0,83950617 2 año
0,11111111 0,88888889 3 año
0,05555556 0,94444444 4 año
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
m ..., 1,i ij dd 
donde
ddd
ddd
 D
 )(pd
m
1j
ijii
mmm1m0
0m0100
0ijij






















D
D



D




t
t
td
d
26
…
…
…
…
…
…
…
…
ENZO CORTE
Máquina de escribir
t toma valores reales 
ENZO CORTE
Máquina de escribir
Se trabaja con probabilidades de transicion que tiendan a 0, delta t tiende a 0 por ser continuo
ENZO CORTE
Máquina de escribir
Los elementos de la diagonal principal de la matriz d se van a calcular como la suma de los elementos de su fila cambiadas de signo
Además por la Probabilidad incondicional de estado
27
 
 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 


 
DD
DD

28
0000 
ddd
d
ddd
 ppp
mmmjm0
i0
0m0j00
mi0 




 
P D 0x =
…
… …
…
…
……
…
…
… …
… …
…
ENZO CORTE
Máquina de escribir
Probabiidades incondicionales definidas
para parametro continuo
Además:
y
p = B x A-1
29
 1000 
1ddd
1ddd
1ddd
 pppp
 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
…
ENZO CORTE
Máquina de escribir
En ultima columna sustituyo por 1s
ENZO CORTE
Máquina de escribir
El ultimo elemento sustituyo por 1
Se tiene un componente electrónico que puede encontrarse en dos estados on y 
off. Son conocidas las probabilidades condicionales de cambio de un estado al 
otro, se quiere conocer el tiempo durante el cual el dispositivo se encuentra en 
cada estado. 
P on-off = 0.4 ( 1 - e –5Dt ) : P off -on = 0.6( 1 – e-5Dt )
Plantee el problema, identifique y formule el modelo completo 
Resuelva e interprete los resultados
Estado 1: Sistema en On
Estado: Sistema en Off
Construyo la matriz P de transición:
𝑃(∆𝑡) = 
∗ ∗
∗ ∗
 
on off
on
off
P on-off = 0.4 ( 1 - e –5Dt )=0.4-0.4 e –5Dt
P on-on = 1-0.4 ( 1 - e –5Dt )=1-0.4+0.4 e –5Dt=0.6+0.4 e –5Dt
P off -on = 0.6( 1 – e-5Dt )=0.6-0.6 e-5Dt
P off -off = 1-0.6( 1 – e-5Dt )=1-0.6+0.6 e-5Dt =0.4+0.6 e-5Dt
Matriz de tasas o intensidades de transición
𝑑(P on − on )
𝑑∆𝑡
 
∆𝑡=0
=
𝑑(0.6 + 0.4𝑒−5∆𝑡)
𝑑∆𝑡
 
∆𝑡=0
=
𝑑(0.6 + 0.4𝑒−5∆𝑡)
𝑑∆𝑡
 
∆𝑡=0
= −0.4𝑒−5∆𝑡 
∆𝑡=0
= −0.4 
 = −0 4
 
 = 0 4
 
𝑑(P off − off )
𝑑∆𝑡
 
∆𝑡=0
=
𝑑(0.4 + 0.6 𝑒−5∆𝑡)
𝑑∆𝑡
 
∆𝑡=0
=
𝑑(0.4 + 0.6𝑒−5∆𝑡)
𝑑∆𝑡
 
∆𝑡=0
= −0.6𝑒−5∆𝑡 
∆𝑡=0
= −0.6 
 = −0 6
 
 = 0 6
 
 = 
−0 4 0 4
0 6 −0 6
 
 = 
−0 4 1
0 6 1
 = 
−1 1
0 6 0,4
 = (0 1)
 
𝑝 = (0,6 0,4) 
pon=0,6 poff=0,4
p = B x A-1
p