• Author / Uploaded
• Jonathan Salinas

Citation preview

18/09/2018

CADENAS DE MARKOV LILIANA DELGADO HIDALGO [email protected]

Universidad del Valle

INTRODUCCIÓN A LAS CADENAS DE MARKOV LILIANA DELGADO HIDALGO [email protected]

Universidad del Valle

1

18/09/2018

ANDREI ANDREYEVICH MARKOV Andrei Andreyevich Markov nació el 14 de junio de 1856 en Ryazan, Rusia y murió el 20 de julio de 1922 en Petrogrado, ahora San Petersburgo. Andrei A. Markov fue un destacado Matemático Graduado de la Universidad de San Petersburgo en 1878. Después de 1900 Markov realizó grandes avances en la teoría de la probabilidad, probando incluso el importante Teorema Central del Limite. Estudió sucesiones de variables mutuamente dependientes, con la esperanza de establecer las leyes límite de probabilidad en su forma más general. Sin embargo Markov es particularmente recordado por sus estudios de las Cadenas de Markov (teoría que desarrolló a sus 51 años), sucesiones de variables aleatorias en las cuales la siguiente variable está determinada por la actual variable pero es independiente de las anteriores. Con esto surge una nueva rama de la teoría de Probabilidades y comienza la teoría de los procesos estocásticos.

QUE UTILIDAD TIENE LAS CADENAS DE MARKOV ?

Se busca una herramienta “telescópica” que permita aproximarnos objetivamente al futuro.

Cadenas de Markov

El análisis de Markov, permite encontrar la probabilidad de que un sistema se encuentre en un estado en particular en un momento dado. Con esta información se puede predecir el comportamiento del sistema a través del tiempo.

Procesos de planeación de largo plazo

2

18/09/2018

CASO PRÁCTICO  Cox, D. R. (2017). The theory of stochastic processes. Routledge.  Considere un componente, por ejemplo una válvula la cual está sujeta a falla

 El componente se inspecciona diariamente y se nota que puede estar funcionando satisfactoriamente, no satisfactoriamente o puede estar fallando  Que información querríamos analizar?  Reemplazar componentes no satisfactorio antes de que falle?

CASO PRÁCTICO  Variable aleatoria de interés?  𝑿𝒕 = 𝒇𝒖𝒏𝒄𝒊𝒐𝒏𝒂𝒎𝒊𝒆𝒏𝒕𝒐 𝒅𝒆𝒍 𝒄𝒐𝒎𝒑𝒐𝒏𝒆𝒏𝒕𝒆 𝒆𝒏 𝒆𝒍 𝒑𝒆𝒓𝒊𝒐𝒅𝒐 𝒕

 Cuáles son las unidades de t ?  diarias  Cuáles son los posibles estados de funcionamiento del componente (de la variable aleatoria)?  Estado 0: satisfactorio  Estado 1: no satisfactorio (es probable que falle pronto)  Estado 2: falla

3

18/09/2018

CASO PRÁCTICO  Suponga que en el periodo t, el componente funciona satisfactoriamente (estado 0)  La probabilidad de que en el periodo t+1 el componente continúe funcionando satisfactoriamente (estado 0) es 𝑃00  La probabilidad de que en el periodo t+1 el componente funcione no satisfactoriamente (estado 1) es 𝑃01  La probabilidad de que en el periodo t+1 el componente este fallando (estado 2) es 𝑃02  𝑃00 + 𝑃01 + 𝑃02 = ?

CASO PRÁCTICO  Suponga que en el periodo t, el componente está funcionando no satisfactoriamente (1)  La probabilidad de que en el periodo t+1 el componente esté funcionando satisfactoriamente (estado 0) es 𝑃10 = ?  La probabilidad de que en el periodo t+1 el componente continúe funcionando no satisfactoriamente (estado 1) es 𝑃11  La probabilidad de que en el periodo t+1 el componente esté fallando (estado 2) es 𝑃12  𝑃10 + 𝑃11 + 𝑃12 = ?

4

18/09/2018

CASO PRÁCTICO  Suponga que en el periodo t, el componente está fallando (estado 2)  La probabilidad de que en el periodo t+1 el componente esté funcionando satisfactoriamente (estado 0) es 𝑃20 = ?  La probabilidad de que en el periodo t+1 el componente esté funcionando no satisfactoriamente (estado 1) es 𝑃21 = ?  La probabilidad de que en el periodo t+1 el componente continúe fallando (estado 2) es 𝑃22 =?  𝑃20 + 𝑃21 + 𝑃22 = ?

PROBABILIDADES DE TRANSICIÓN  A las probabilidades 𝑃𝑖𝑗 se les llama probabilidad de Transición del estado i al estado j  Las probabilidades 𝑃𝑖𝑗 son probabilidades condicionales 𝑷𝒊𝒋 = 𝑷(𝒙𝒕+𝟏 = 𝒋Τ𝑿𝒕 = 𝒊)  Suponga que la probabilidad 𝑷𝒊𝒋 = 𝑷(𝒙𝒕+𝟏 = 𝒋Τ𝑿𝒕 = 𝒊) es igual para cualquier t, es decir que 𝑷𝒊𝒋 son probabilidades constantes que no dependen de t, entonces: P(X1=j / X0=i) = P(X2=j / X1=i) = …= P(Xt+1=j / Xt=i)  𝑷𝒊𝒋 es estacionaria  Vamos a asumir que 𝑷𝒊𝒋 es estacionaria

Universidad del Valle

5

18/09/2018

PROBABILIDADES DE TRANSICIÓN

Observe que al evaluar 𝑷𝒊𝒋 se analiza la transición de un estado a otro en períodos de tiempos consecutivos, es decir, se estudian los instantes de tiempo t y t+1.

Por tanto, a 𝑷𝒊𝒋 suele en algunas ocasiones escribirse con uno, (1), arriba indicando que entre un estado y otro hay un solo periodo de tiempo (ó un paso)

(1)

pij  pij

LA MEMORIA TEMPORAL DE LA CADENA DE MARKOV  Suponga que las probabilidades de transición 𝑷𝒊𝒋 = 𝑷(𝒙𝒕+𝟏 = 𝒋Τ𝑿𝒕 = 𝒊) son independientes de la historia del funcionamiento del componente en un periodo anterior al periodo t

Xt+1=j , Xt=i, Estado Futuro

Estado Actual

Xt-1=m,

Xt-2=k,……..,X0=p

Estados Pasados

 Entonces este tipo especial de proceso es una cadena de Markov  El estado futuro de la variable en el tiempo t+1, está condicionado únicamente por el “recuerdo” que se tiene de lo ocurrido en el tiempo t. Universidad del Valle

6

18/09/2018

MATRIZ DE PROBABILIDADES DE TRANSICIÓN DE “UN PASO” Matriz de Probabilidades de Transición de un paso de la Cadena de Markov para el caso práctico

𝑃00 𝑃𝑖𝑗 = 𝑃10 𝑃20

𝑃01 𝑃11 𝑃21

𝑃02 𝑃12 𝑃22

Habíamos dicho que… 𝑃00 + 𝑃01 + 𝑃02 = 1

𝑃10 + 𝑃11 + 𝑃12 = 1

𝑃20 + 𝑃21 + 𝑃22 = 1

Ajá! No lo recuerda?!

Pero cuál es el fundamento?

MATRIZ DE PROBABILIDADES DE TRANSICIÓN DE “UN PASO”

Cada fila de Pij corresponde a un espacio muestral

𝑃 𝑋𝑡+1 = 0Τ𝑋𝑡 = 0 + 𝑃 𝑋𝑡+1 = 1Τ𝑋𝑡 = 0 + 𝑃 𝑋𝑡+1 = 2Τ𝑋𝑡 = 0 = 1 𝑃 𝑋𝑡+1 = 0Τ𝑋𝑡 = 1 + 𝑃 𝑋𝑡+1 = 1Τ𝑋𝑡 = 1 + 𝑃 𝑋𝑡+1 = 2Τ𝑋𝑡 = 1 = 1 𝑃 𝑋𝑡+1 = 0Τ𝑋𝑡 = 2 + 𝑃 𝑋𝑡+1 = 1Τ𝑋𝑡 = 2 + 𝑃 𝑋𝑡+1 = 2Τ𝑋𝑡 = 2 = 1 Se debe satisfacer: 1) pij  0 para todo i, j

2)  pij

1

para todo i

j

7

18/09/2018

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO”

Después de muchos estudios sobre el clima, hemos visto que si un día está soleado, en el 70% de los casos el día siguiente continua soleado y en el 30% se pone nublado.

También nos hemos fijamos en que si un día está nublado, la probabilidad de que esté soleado el día siguiente es 0,6 y la probabilidad de que se ponga nublado es 0,4. Si hoy está nublado, ¿cuál es la probabilidad de que mañana continúe nublado?

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO” Estados:

Soleado y Nublado

Periodo de transición entre estados: P(X1 = soleado/ X0 = soleado)=

0.7

P(X1 = nublado/ X0 = soleado)=

0.3

P(X1 = soleado/ X0 = nublado)=

0.6

P(X1 = nublado/ X0 = nublado)=

0.4

Pt (11)

=

Un día

Estados

Soleado

Nublado

Soleado

0,7

0,3

Nublado

0,6

0,4

Si hoy está nublado, ¿cuál es la probabilidad de que mañana continúe nublado?

8

18/09/2018

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO” Ley Inicial del Sistema: Hoy está nublado (condición inicial) y por tanto la ley inicial es:

 soleado(0)  P( X 0  soleado)  0  nublado(0)  P( X 0  nublado)  1  (0)   soleado(0),  nublado(0)  0,1 La pregunta entonces es, dada la ley inicial en t = 0, hallar las Leyes de Probabilidad un día después, es decir, en t = 1. Para lograr esto debemos recordar el Teorema de Probabilidad Total, que lo aplicaríamos de la siguiente forma:

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO” P(X 1  nublado)  P( X 0  nublado ) xP ( X 1  nublado / X 0  nublado )  P( X 0  soleado ) xP ( X 1  nublado / X 0  soleado ) Por lo tanto : P(X 1  nublado)  (1) x(0.4)  (0) x(0.3)  0.4

Se puede notar que mañana hay más probabilidad de que esté el día soleado. Si calcula en este caso P (X1 = soleado) se dará cuenta que es igual al 0.6, y por lo tanto la Ley de Probabilidades el día de mañana dada la condición inicial de nublado será : 𝜋 1 = 𝜋𝑠𝑜𝑙𝑒𝑎𝑑𝑜 1 , 𝜋𝑛𝑢𝑏𝑙𝑎𝑑𝑜 1

= [0.6, 0.4]

9

18/09/2018

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO” CONCLUSIÓN

Ejercicios de construcción de matrices de transición

10

18/09/2018

Juego de apuestas En el tiempo 0 tengo $ 2 y en los tiempos 1,2,3,... participo en un juego en el que apuesto $1. Gano el juego (y gano $1) con probabilidad p y lo pierdo (perdiendo lo apostado) con probabilidad 1-p. Mi meta es aumentar mi capital hasta $4 y tan pronto lo logre me salgo del juego. También salgo cuando me arruine (capital $0). Encuentre la matriz de transición Xn : mi capital inmediatamente después del juego n Estados del proceso =

Matriz de transición

{0, 1, 2, 3, 4}

0 0  1  p 1  p 0  P  0 1 p 0  0 1 p  0  0 0 0 

0 0  0 0 p 0  0 p 0 1 

El Profesor Un profesor de Modelos Estocásticos tiene tres preguntas claves en sus exámenes y una de ellas sale en cada examen que él realiza. Los estudiantes conocen muy bien sus extraños hábitos: Él nunca utiliza la misma pregunta en dos exámenes consecutivos. Si utilizó la pregunta No. 1 en el último examen, arroja una moneda al aire y si sale cara usa la pregunta No. 2. Si había usado la pregunta No. 2, arroja dos monedas al aire y si salen dos caras, utiliza la pregunta No. 3 y, finalmente, si había usado la pregunta No. 3, arroja tres monedas al aire y si salen tres caras, usa la pregunta No. 1. Elabore la matriz de transición de un paso para el problema descrito anteriormente.

11

18/09/2018

Costurera

Una costurera trabaja exclusivamente en una fase del proceso de producción de un diseño especial de prendas de vestir. Esta fase requiere exactamente 30 minutos para terminar una prenda. Cada 30 minutos llega un mensajero a la mesa de la costurera para recoger todas aquellas prendas que estén terminadas y para entregar las nuevas prendas que deben ser cosidas. El número de nuevas prendas que lleva el mensajero es aleatorio: 30% del tiempo el mensajero llega sin prendas; 50% del tiempo el mensajero trae una sola prenda para dejar y el 20% restante del tiempo el mensajero trae dos prendas para la costurera. Sin embargo, el mensajero tiene instrucciones de nunca dejar más de tres prendas (si es que las llevase) juntas no terminadas a la costurera y simplemente llevarlas a otra costurera que sí tenga capacidad.

Grupo Musical Un estudiante que vio el curso de modelos estocásticos ha decidido dedicarse a la música, y junto a unos amigos formó el grupo “Jorge y los Markovianos”. Actualmente se limitan a tocar los fines de semana en algunos bares de la capital, siendo una de tantas bandas desconocidas que existen en el país. Cada mes existe una probabilidad “q” que un empresario de algún sello musical nacional los escuche y decida apoyarlos para grabar y realizar giras para cantar de Arica a Punta Arenas. Si tal cosa ocurre pasarían a ser una banda conocida a nivel nacional. Una banda que es conocida a nivel nacional corre el riesgo de perder el apoyo del sello nacional que la patrocina, con lo cual volvería a ser una banda desconocida. Cada mes, la probabilidad que esto ocurra es r. Por otro lado, una banda conocida a nivel nacional puede llegar a llamar la atención del representante de un sello musical internacional, el cual podría decidir patrocinarlos. De ser así la banda pasaría a ser conocida a nivel internacional. Cada mes existe una probabilidad s que esto ocurra (s +r < 1).

12

18/09/2018

Grupo Musical

Una banda que es conocida internacionalmente nunca dejará de serlo. Sin embargo podemos distinguir dos categorías entre ellas: las que están de moda y las que no. Una banda internacionalmente conocida que está de moda en un mes dado seguirá estando de moda al mes siguiente con probabilidad t. Una banda conocida a nivel internacional que no está de moda en un mes dado pasará a estar de moda al mes siguiente con probabilidad u. El primer mes que una banda se hace conocida a nivel internacional nunca está de moda. Una banda sólo percibe utilidades (equivalentes a K[$]) en los meses que es conocida internacionalmente y está de moda (parte de esas utilidades corresponden a una satisfacción de su ego). Construya una cadena de Markov que represente la trayectoria de la banda de Jorge y que permita predecir si en un mes dado percibirán utilidades o no

13