INVESTIGACIÓN OPERATIVA
TEMA 3
Introducción a las cadenas de Markov de primer orden
1. Definición de cadenas de Markov
2. Tipos de estados y de cadenas de Markov.
Propiedades
3. Comportamiento a largo plazo de cadenas de Markov.
Aplicaciones
4. Comportamiento a corto plazo de cadenas de Markov.
Tiempos y probabilidades del primer paso
5. El caso particular de las cadenas absorbentes.
Aplicaciones
6. Estudio de casos reales de aplicación. Los procesos de
markov en los análisis coste-efectividad
Beatriz Gonzalez Lopez-Valcarcel
Introducción
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: reparto del mercado entre marcas; dinámica
de las averías de máquinas para decidir política de
mantenimiento; evolución de una enfermedad,…
Beatriz Gonzalez Lopez-Valcarcel
1
1. Definición de Cadena de Markov
• Una Cadena de Markov (CM) es:
• Un proceso estocástico
• Con un número finito de estados (M)
• Con probabilidades de transición estacionarias
• Que tiene la propiedad markoviana
Beatriz Gonzalez Lopez-Valcarcel
1
Proceso estocástico:
• Es un conjunto o sucesión de variables aleatorias: {X(t)CG
} definidas en un mismo espacio de probabilidad.
• Normalmente el índice t representa un tiempo y X(t) el
estado del proceso estocástico en el instante t.
• El proceso puede ser de tiempo discreto o continuo si G es
discreto o continuo.
• Si el proceso es de tiempo discreto, usamos enteros para
representar el índice: {X1, X2, ...}
Beatriz Gonzalez Lopez-Valcarcel
1
Ejemplos de procesos estocásticos:
1. Serie mensual de ventas de un producto
2. Estado de una máquina al final de cada semana
(funciona/averiada)
3. Nº de clientes esperando en una cola cada 30 segundos
4. Marca de detergente que compra un consumidor cada vez
que hace la compra. Se supone que existen 7 marcas
diferentes
5. Nº de unidades en almacén al finalizar la semana
Beatriz Gonzalez Lopez-Valcarcel
1
ELEMENTOS DE UNA CADENA
DE MARKOV
–
Un conjunto finito de M estados, exhaustivos y mutuamente
excluyentes (ejemplo: estados de la enfermedad)
–
Ciclo de markov (“paso”) : periodo de tiempo que sirve de
base para examinar las transiciones entre estados (ejemplo, un
mes)
–
Probabilidades de transición entre estados, en un ciclo (matriz
P)
–
Distribución inicial del sistema entre los M estados posibles
1
PROPIEDAD MARKOVIANA
Un proceso estocástico tiene la propiedad markoviana si las
probabilidades de transición en un paso sólo dependen del estado
del sistema en el período anterior (memoria limitada)
1
PROPIEDAD MARKOVIANA
P(n) es la matriz de transición en n pasos, de orden (M+1)x(M+1)
1
PROPIEDAD MARKOVIANA
1
PROPIEDAD MARKOVIANA
1
LAS CADENAS DE MARKOV
SON UN CASO PARTICULAR
DE MODELOS DE MARKOV
Tipos de modelos de Markov:
•
Procesos de Markov (Modelos semimarkovianos): Las probabilidades de transición
entre estados pueden variar a medida que
transcurren más ciclos
–
•
Ejemplo: para modelizar la esperanza de vida, el riesgo
de muerte aumenta con la edad
Cadenas de Markov: Las probabilidades de
transición se suponen constantes a lo largo del
tiempo
1
PROPIEDAD MARKOVIANA
Ejemplos:
Comportamiento (sube/baja) del precio de las
acciones hoy depende de lo ocurrido ayer
Problema de la ruina de un jugador de casino
Elección de marca: Con qué línea aérea volar a
Madrid?
Ejercicio 1: Tres agencias de viaje disponen de información respecto
de los desplazamientos en vacaciones de semana santa.
1
Estado futuro n=1
Estado actual n=0
No viajar
V. entre islas
V. fuera
No viajar
40
20
40
V. entre islas
50
10
40
V. fuera
10
70
20
a) Supuestos necesarios para considerar esta situación como cadena
de Markov de primer orden
b) Calcular la probabilidad de que los clientes que no han viajado
estas vacaciones lo hagan fuera de las islas dentro de 2 años.
1
Ejercicio 2: La carrera de diplomado en CCEE tiene 3 cursos. A
partir de los datos facilitados por el decanato del centro se sabe que el
35% y el 26% de los alumnos de primero y segundo abandonarán los
estudios. El 28% de los alumnos de primero repiten curso, siendo
este porcentaje del 20% y 30% para los alumnos de segundo y
tercero respectivamente.
1
EJEMPLO 1: EL REPARTO DEL
MERCADO A LARGO PLAZO
EN UN OLIGOPOLIO
Tres laboratorios farmacéuticos (A,B y C) que compiten en un principio activo
(mismo conjunto homogéneo en la orden de precios de referencia). Hoy
sus cuotas de mercado son 30%, 20% y 50% respectivamente
Las filas suman 1
Matriz de transición en
un paso (ciclo)
Ciclo: Mes
A
A
B
C
B
0,8
0,15
0,13
C
0,1
0,82
0,12
0,1
0,03
0,75
¿Cómo se repartirán el mercado dentro de 1
mes, 6 meses, 1 año?, ¿A largo plazo?
1
EJEMPLO 2: LA EVOLUCIÓN CLÍNICA DE LOS
PACIENTES CON VÁLVULA CARDIACA
SOMETIDOS A TRATAMIENTO ANTICOAGULANTE
CON
SECUELAS
BIEN
3 estados (1 absorbente, 2 transitorios)
MUERTO
Ciclo=mes
Utilidades = Nivel salud
Distribución inicial de la cohorte
(N=10.000): todos bien
1
EJEMPLO 2: LA EVOLUCIÓN CLÍNICA DE LOS
PACIENTES CON VÁLVULA CARDIACA
SOMETIDOS A TRATAMIENTO ANTICOAGULANTE
CON
SECUELAS
BIEN
3 estados (1 absorbente, 2 transitorios)
MUERTO
Ciclo=mes
Utilidades = Nivel salud
Distribución inicial de la cohorte
(N=10.000): todos bien
1
EJEMPLO 2: LA EVOLUCIÓN CLÍNICA DE LOS
PACIENTES CON VÁLVULA CARDIACA
SOMETIDOS A TRATAMIENTO ANTICOAGULANTE
0.6
0.6
BIEN
0.2
0.2
CON
SECUELAS
3 estados (1 absorbente, 2 transitorios)
MUERTO
Ciclo=mes
Utilidades = Nivel salud
Distribución inicial de la cohorte
(N=10.000): todos bien
1
EJEMPLO 1: EL REPARTO DEL
MERCADO A LARGO PLAZO
EN UN OLIGOPOLIO
Tres laboratorios farmacéuticos (A,B y C) que compiten en un principio activo
(mismo conjunto homogéneo en la orden de precios de referencia). Hoy
sus cuotas de mercado son 30%, 20% y 50% respectivamente
Las filas suman 1
Matriz de
transición en un
ciclo (P)
Ciclo: Mes
A
A
B
C
B
0,8
0,15
0,13
C
0,1
0,82
0,12
0,1
0,03
0,75
¿Cómo se repartirán el mercado dentro de 1
mes, 6 meses, 1 año?, ¿A largo plazo?
1
EJEMPLO 1: EL REPARTO DEL
MERCADO A LARGO PLAZO
EN UN OLIGOPOLIO
•
Este es un ejemplo de cadena de Markov irreductible y ergódica.
Todos los estados son recurrentes y están comunicados entre sí,
formando una sola clase.Hay solución de estado estable (reparto del
mercado a largo plazo, independiente de la situación inicial)
Reparto del mercado
después de n ciclos
= P0*Pn
1 mes.....P1= [0.3350 0.2540 0.4110]
2 meses ....p2 =[ 0.3595 0.2911 0.3494]
6 meses ...... p6 =[ 0.4030 0.3543 0.2427]
1 año ....... p12 = [ 0.4150 0.3704 0.2146]
2 años ...... p24 =[ 0.4165 0.3722 0.2113]
Solución de estado estable
3 años ....... p36 =[ 0.4165
0.3722 0.21131]
1
EJEMPLO 3: EL HÁBITO TABÁQUICO
DE LOS JÓVENES
Lo ha probado, Fuma menos de
Fuma los fines
pero ahora no
una vez por
Fuma diariamente
de semana
fuma
semana
77.7%
17.2%
3.2%
0.9%
1.0%
Nunca lo ha
probado
Nunca lo ha probado
Lo ha probado, pero ahora
no fuma
Fuma menos de una vez
por semana
Fuma los fines de semana
Fuma diariamente
Total
Total
100.0%
0.0%
75.0%
12.2%
4.7%
8.1%
100.0%
0.0%
0.0%
0.0%
50.4%
34.0%
26.5%
6.3%
31.8%
22.0%
17.6%
8.3%
6.7%
12.0%
26.5%
0.0%
3.0%
32.0%
29.4%
85.4%
8.1%
100.0%
100.0%
100.0%
100.0%
5 estados (1 transitorio, 4 recurrentes)
Ciclo= un año
Distribución inicial de la cohorte (N=1.340):
(0.58 0.28 0.05 0.03 0.06)
2 Tipos de estados y de cadenas de markov de primer orden
•
Para clasificar los estados y las CM tenemos que definir
algunos conceptos:
• Tiempos del primer paso y de recurrencia
• Accesibilidad y comunicación entre estados
Tiempos del primer paso/recurrencia (Corto plazo)
2
Con lo visto hasta el momento podemos calcular la probabilidad,
dado que el proceso se encuentra en el estado i, de que el proceso se
encuentre en el estado j después de n periodos Pij(n).
2 EJEMPLO: Un vendedor de cámaras fotográficas lleva acabo la
siguiente política de inventario. Mantiene durante la semana de
trabajo hasta un máximo de 3 cámaras en el almacén para su venta. Si
al final de la semana le quedan en el almacén alguna cámara entonces
no pide ninguna al fabricante. De partida en el almacén hay 3
cámaras (x0=3).
a) Comenta el contenido de la matriz
de transición P facilitada por el
comercio.
b) Sabiendo que hay dos cámaras al
final de la primera semana (x1=2),
(x2=1), (x3=0), (x4=3) y (x5=1).
Obtener el tiempo de primera
pasada para ir del estado 3 al 1, y
el tiempo de recurrencia del
estado 3.
Tiempos de primera pasada/recurrencia (Corto plazo)
2
En general podemos considerar a los tiempos de primera pasada
como variables aleatorias, por tanto con una distribución de
probabilidad asociada a ellos. Dichas distribuciones de
probabilidad dependerán de las probabilidades de transición del
proceso.
fij(1)=pij(1)=pij
fij(2)=pij(2)-fij(1)pij
.............................................
fij(n)=pij(n)-fij(1)pij(n-1)-fij(2)pij(n-2)....-fij(n-1)pij
Tiempos de primera pasada/recurrencia (Corto plazo)
2
Como generalmente es bastante engorroso calcular las fij(n) para
todas las n, se suele optar por obtener el tiempo esperado de
primera pasada del estado i al estado j
Tipos de estados y Cadenas de Markov
2
Podemos considerar fij(n) para (n=1,2,..) como la función de
probabilidad de la variable aleatoria tiempo de primera pasada

(n)

(n)
Una vez que el proceso se
encuentra en el estado i no lo
abandona
Una vez que el proceso se
encuentra en el estado i existe
una prob.>0 de no regresar
2
Ejemplo Identifica los distintos estados en la siguiente
matriz de transición.
Estados
P
0
1
2
3
4
0
0.25
0.5
0
0
1
1
0.75
0.5
0
0
0
2
0
0
1
0.33333333
0
3
0
0
0
0.66666667
0
4
0
0
0
0
0
2
Tipos de estados y Cadenas de Markov
2
Tipos de estados y Cadenas de Markov
2
Tipos de estados y Cadenas de Markov.
2
Tipos de estados y Cadenas de Markov.
3
Comportamiento a largo plazo de las Cadenas de
Markov
2
Comportamiento a largo plazo de las Cadenas de
Markov
4
Comportamiento a largo plazo de las
Cadenas de Markov: el caso de las cadenas
absorbentes
• CM absorbente:
– Tiene al menos un estado absorbente
– Desde cualquier estado no absorbente se puede acceder
a algún estado absorbente
• A largo plazo, termina en absorción con
probabilidad 1
• Interesa calcular:
– Probabilidad de absorción por cada estado absorbente
– Numero esperado de pasos antes de la absorción
4
Comportamiento a largo plazo de las
Cadenas de Markov: el caso de las cadenas
absorbentes
EJEMPLOS DE APLICACIONES
CÓMO HACER EL MODELO
REALISTA
•
Propiedad
Ingredientes de una cadena de markov:
markoviana: falta de
–
Conjunto de K estados exhaustivos y mutuamente
excluyentes
memoria
definen las posibles situaciones (ej. Bien-discapacitado-muerto)
(¿Realista?...)
–
Ciclo: periodo de tiempo en el que ocurren transiciones entre
estados (ej: un mes)
–
Probabilidades de transición entre estados en un ciclo
• Se suponen constantes en el
tiempo, e idénticas para todos los pacientes
•
–
Sus valores forman la matriz de transición en un paso (P)
Distribución inicial de la cohorte de pacientes entre los K
estados
EJEMPLO 1: LA EVOLUCIÓN CLÍNICA DE LOS
PACIENTES CON VÁLVULA CARDIACA
SOMETIDOS A TRATAMIENTO ANTICOAGULANTE
Complicando el modelo para hacerlo más realista
CON
SECUELAS
BIEN
MUERTO
Se incluye un estado transitorio de
proceso agudo (embolia o hemorragia
interna)
EJEMPLO 1: LA EVOLUCIÓN CLÍNICA DE LOS
PACIENTES CON VÁLVULA CARDIACA
SOMETIDOS A TRATAMIENTO ANTICOAGULANTE
Complicando el modelo para hacerlo más realista
BIEN
ACCIDENTE
CEREBRAL
VASCULAR
MUERTO
CON
SECUELAS
Estado transitorio ACV: para un suceso
que tiene solo efectos a corto
plazo
Dos usos:
1)
Incorporar un valor específico de
la utilidad (o coste)
2)
Asignar temporalmente diferentes
probabilidades de transición
CONCEPTOS BÁSICOS
•
Esta limitación generalmente
puede resolverse definiendo
Ingredientes de una cadenaestados
de markov:
distintos para
–
Conjunto de K estados exhaustivos
y mutuamente
excluyentes
pacientes
con distintos
definen las posibles situaciones (ej. antecedentes
Bien-discapacitado-muerto)
–
Ciclo: periodo de tiempo en el que ocurren transiciones entre
estados (ej: un mes)
–
Probabilidades de transición entre estados en un ciclo
•
Se suponen constantes en el tiempo, e
idénticas para
todos los pacientes
•
–
Sus valores forman la matriz de transición en un paso (P)
Distribución inicial de la cohorte de pacientes entre los K
estados
Software y bibliografía
• Usaremos QSB
• Un excelente texto para este tema es el de
Hillier y Lieberman (está referenciado en el
programa)
Descargar

Cadenas de Markov