Cap 1- Cadenas De Markov.pdf

Universidad Católica Boliviana

Investigación Operativa II Mgr. Ramiro Luján M.

Capítulo 1 – Procesos de Markov Métodos Cuantitativos para los Negocios - Anderson, Sweeney, Williams; Slides: J. Loucks

QUANTITATIVE METHODS FOR BUSINESS 8e

Cochabamba, 2019

Slide 1

Capítulo 1 Procesos de Markov   

Probabilidades de Transición Probabilidades de Estado Estable (Steady-State) Estados Absorbentes • Matriz de Transición con Sub matrices • Matriz Fundamental

Slide 2

Capítulo 1 Glosario Procesos de Markov   



Ensayos: Eventos que desencadenan las transiciones del sistema de un estado a otro. Estado del Sistema: Condición del sistema en cualquier ensayo o periodo particular Probabilidad de transición: Dado que el sistema está en el estado i durante un periodo, la probabilidad de transición pij es la probabilidad de que el sistema esté en el estado j durante el siguiente periodo Probabilidad de estado: Probabilidad de que el sistema esté en cualquier estado particular. (Es decir, i (n) es la probabilidad de que el sistema esté en el estado i en el periodo n)

Slide 3

Capítulo 1 Glosario Procesos de Markov 

Probabilidad de estado estable: Probabilidad de que el sistema esté en cualquier estado particular después de un número grande de transiciones. Una vez que se ha alcanzado el estado estable, las probabilidades de estado no cambian de un periodo a otro.

Slide 4

Procesos de Markov 

El Objetivo de este capítulo es que el estudiante, cuente con una herramienta útil, para estudiar la evolución de sistemas a lo largo de ensayos repetidos, los que a menudo, son periodos sucesivos donde el estado del sistema en cualquier periodo particular no puede determinarse con certeza. • Probabilidad de que una máquina esté funcionando el siguiente periodo • Probabilidad de que una persona que hoy compra una marca A, mañana compre la marca B

Slide 5

Procesos de Markov 

El capítulo se restringe a situaciones consistentes en una cantidad finita de estados, en los que permanecen constantes las probabilidades de transición a lo largo del tiempo y la probabilidad de estar en un estado particular en cualquier periodo, depende únicamente del estado en el periodo inmediatamente anterior. A esto se conoce como Cadenas de Markov con probabilidades de transición estacionarias. • Análisis de participación en el mercado • Análisis de cuentas por cobrar

Slide 6

Probabilidades de Transición 



Las Probabilidades de transición gobiernan la manera en la cual el estado de un sistema cambia de una etapa a la siguiente. Esto es representado por la matriz de transición. Un sistema tiene una cadena finita de Markov con probabilidades de transición estacionaria si: • Hay un número finito de estados, • Las probabilidades de transición permanecen constantes de una etapa a la otra y • La probabilidad de que un proceso esté en un estado particular en la etapa n+1 está completamente determinada por el estado del proceso en la etapa n (y no por el estado en la etapa n-1). Esto se refiere como la propiedad sin memoria. Slide 7

Probabilidades de Estado Estable 

Las probabilidades de estado en cualquier etapa de un proceso puede ser calculada recursivamente multiplicando el estado inicial de probabilidades por el estado del proceso en la etapa n. 𝜋𝑖 𝑛 = 𝑃𝑟𝑜𝑏. 𝑠𝑖𝑠𝑡. 𝑒𝑠𝑡é 𝑒𝑛 𝑒𝑙 𝑒𝑠𝑡𝑎𝑑𝑜 𝑖 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑛 𝜋 𝑛+1 =𝜋 𝑛 𝑃



La probabilidad de que un sistema permanezca en un estado particular luego de un gran número de etapas es llamado probabilidad de estado estable. Slide 8

Probabilidades de Estado Estable 

Las probabilidades de estado estable pueden ser halladas resolviendo el sistema de ecuaciones P =  junto con la condición de las probabilidades cuya suma debe ser i = 1. Aquí la matriz P es la matriz de probabilidades de transición y el vector , es el vector de probabilidades de estado estable.

Slide 9

Grafos de Transición P11 P12 1

P22

P21

2

P2m P13

P32 Pm2

P31

P23

P3m 3

m Pm3

P1m P33 P12 Pm1

P22

P11 1

P21

2

P1m Pm2 Pm1

P2m m Pmm

Slide 10

Proceso Ergódigo en una CM

1

2

3

4

5

Un PROCESO ERGÓDICO describe matemáticamente aquel proceso donde es posible avanzar desde un estado cualesquiera hacia cualquier otro de manera no recurrente Slide 11

Quiz 1 



Como podemos clasificar a las Cadenas de Markov? • Discretas y aleatorias • Contínuas y Discretas • Contínuas y Corrientes Las Cadenas de Markov son técnicas que me permiten: • Calcular de manera determinista los eventos futuros • Analizar las probabilidades de eventos • Manejar probabilidades de ocurrencia futura mediante el análisis de las probabilidades conocidas en el presente

Slide 12

Quiz 1 



La Matriz de Probabilidad de transición expresa: • Cálculos unidimensionales de las variables aleatorias de manera secuencial • Las probabilidades de que el sistema cambie de un periodo al siguiente • La evolución del sistema en instantes bien identificados del tiempo Una Cadena ERGÓDICA puede tener: • Estados absorbentes • Estados transitorios no recurrentes • Estados transitorios y estados absorbentes

Slide 13

Ejemplo: Hardware North’s Henry, un persistente hombre de ventas, llama a la tienda de Hardware North's una vez a la semana esperando hablar con la agente de compras de la tienda, Shirley. Si Shirley no acepta la llamada de Henry esta semana, la probabilidad de que ella haga lo mismo la siguiente semana es .35. Por otra parte, si ella acepta la llamada de Henry esta semana, la probabilidad de que no lo haga la siguiente semana es .20.

Slide 14

Ejemplo: Hardware North’s 

Matriz de Transición Next Week's Call Rechaza Acepta

This Week's Call

Rechaza

.35

.65

Acepta

.20

.80

Slide 15

Ejemplo: Hardware North’s 

Probabilidades de Estado Estable • Pregunta Cuántas veces al año espera Henry hablar con Shirley? • Respuesta Para encontrar el número esperado de llamadas aceptadas por año, encuentre la proporción (probabilidad) de largo plazo de que una llamada sea aceptada y multiplíquela por 52 semanas. . . . continua

Slide 16

Ejemplo: Hardware North’s 

Probabilidades de Estado Estable • Respuesta (continuación) Sea 1 = la proporción a largo plazo de llamadas rechazadas 2 = la proporción de largo plazo de llamadas aceptadas Luego, .35 .65 [ ] = [ ] .20 .80

Slide 17

Ejemplo: Hardware North’s 

Probabilidades de Estado Estable • Respuesta (continuación) Entonces,  +  =  (1)  +  =  (2) y,  +  = 1 (3) Resuelva usando las ecuaciones (2) y (3), (ecuación 1 es redundante), sustituyendo  = 1 -  dentro de (2) para obtener: .65(1 - 2) +  = 2 Esto dá  = .76471. Sustituyendo dentro la (3) obtenemos  = .23529. Entonces el número esperado de llamadas aceptadas este año es (.76471)(52) = 39.76 o cerca de 40. Slide 18

Ejemplo: Hardware North’s 

Probabilidad de Estado • Pregunta Cuál es la probabilidad de que Shirley acepte las siguientes dos llamadas de Henry si es que ella no aceptó su llamada esta semana? • Respuesta RECHAZA .35 RECHAZA .35

ACEPTA .65

RECHAZA

RECHAZA .20 ACEPTA .65

P = .35(.35) = .1225

P = .35(.65) = .2275 P = .65(.20) = .1300

ACEPTA

.80

P = .65(.80) = .5200 Slide 19

Ejemplo: Hardware North’s 

Probabilidad de Estado • Pregunta Cuál es la probabilidad de que Shirley acepte exactamente una de las siguientes dos llamadas de Henry si es que ella acepta su llamada esta semana? • Respuesta La probabilidad de que exactamente una de las siguientes dos llamadas sea aceptada, si esta semana la llamada fue aceptada, puede ser calculada de la siguiente manera: (Aceptar la llamada la siguiente semana y rechazar la subsiguiente) y (rechazar la siguiente semana y aceptar la subsiguiente semana) = .13 + .16 = .29 -- 0,2*0,65+0,8*0,2 Slide 20

Estados Absorbentes - Glosario





Estado Absorbente: Se dice que un estado es absorbente si la probabilidad de hacer una transición para salir de ese estado es cero. Por tanto, una vez que el sistema ha hecho una transición a un estado absorbente, permanecerá ahí. Matriz Fundamental: Matriz necesaria para el cálculo de probabilidades asociadas con los estados absorbentes de un proceso de Markov.

Slide 21

Estados Absorbentes 



Un estado absorbente es aquel en el cual la probabilidad de que el proceso permanezca en ese estado una vez que se entra en ese estado es 1. Si existe más de un estado absorbente, entonces la condición de estado estable independiente de las condiciones iniciales del estado no existen.

Slide 22

Matrices de Transición con Sub matrices 

Si una cadena de Markov tiene ambos estados, absorbentes y no absorbentes, los estados pueden ser reordenados de tal manera que la Matriz de Transición pueda ser escrita como la siguiente composición de cuatro sub matrices: I, 0, R, y Q: I 0 R Q

Slide 23

Matrices de Transición con Sub matrices I = la matriz de identidad indica aquella que una vez que se ha alcanzado un estado absorbente, siempre se permanece en ese estado. 0 = la matriz cero representa la probabilidad 0 de pasar de un estado absorbente a uno no absorbente R = las probabilidades de transición de un estado no absorbente a uno absorbente Q = las probabilidades de transición entre estados no absorbentes

Slide 24

La Matriz Fundamental y NR 



La matriz fundamental, N, es la inversa de la diferencia entre la matriz identidad y la matriz Q: N = (I - Q )-1 La matriz NR, es el producto de la matriz fundamental y la matriz R, proporciona las probabilidades de moverse eventualmente de cada estado no absorbente a cada estado absorbente. Multiplicando cualquier vector de probabilidades inicial de estado no absorbente por NR proporciona el vector de probabilidades de que el proceso eventualmente alcance cada uno de los estados absorbentes. Estos cálculos permiten análisis económicos de sistemas y políticas. Slide 25

Ejemplo: Jetair Aerospace El vice presidente de personal en Jetair Aerospace se ha fijado que las promociones de personal anuales pueden ser modeladas por un proceso de Markov. La matriz de transición es:

Siguiente Año

Año Actual Misma Posición Promoción Retiro Abandono Despido

Misma Posición Promoción Retiro Aba. Desp.

.55 .70 0 0 0

.10 .20 0 0 0

.05 0 1 0 0

.20 .10 0 1 0

.10 0 0 0 1 Slide 26

Ejemplo: Jetair Aerospace 

Matriz de Transición

Next Year Retire Quit Fired Same Promotion Current Year Retire Quit Fired

1 0 0

0 1 0

0 0 1

0 0 0

0 0 0

Same Promotion

.05 0

.20 .10

.10 0

.55 .70

.10 .20

Slide 27

Ejemplo: Jetair Aerospace 

Matriz Fundamental

-1 1

0

N = (I - Q )-1 =

.55

.10

.70

.20

0

1

-1

.45 -.10 =

-.70 .80

Slide 28

Ejemplo: Jetair Aerospace 

Matriz Fundamental El determinante, d = aa - aa = (.45)(.80) - (-.70)(-.10) = .29 Entonces, .80/.29 .10/.29 2.76 .34 N = = .70/.29 .45/.29 2.41 1.55

Slide 29

Ejemplo: Jetair Aerospace 

Matriz NR Las probabilidades de moverse de un estado no absorbente a un estado absorbente están dadas por: 2.76

.34

NR =

.05

.20

.10

0

.10

0

x 2.41 1.55

Retire

Quit

Fired

Same

.14

.59

.28

Promotion

.12

.64

.24

=

Slide 30

Ejemplo: Jetair Aerospace 

Estados Absorbentes • Pregunta Cuál es la probabilidad de que alguien que recientemente fue promovido, eventualmente se retire? . . . Abandone(quitting)? . . . Sea despedido (being fired)? • Respuesta Las respuestas están dadas por la fila inferior de la matriz NR. Las respuestas son entonces:

Eventually Retiring = .12 Eventually Quitting = .64 Eventually Being Fired = .24 Slide 31

Fin del capítulo 1

Gracias

Mgr. Ramiro Luján - UCB

Slide 32