L UPn RZlx Li YNu KGc Jc Sg 1vq K2ovk C0Z-Lectura fundamental 3 PDF

Preview

Summary

asdasd...

Description

Cadenas de Markov en tiempo discreto

Contenido 1

Cadenas de Markov en Tiempo Discreto

Palabras clave: Cadenas de Markov, proc

Dentro de los diferentes procesos estocásticos utilizados para el estudio del comportamiento de los sistemas dinámicos, las Cadenas de Markov ocupan un lugar importante. La simplicidad de su modelamiento y su eficiencia computacional han favorecido su uso en todo tipo de sistemas, desde los productivos, logísticos, de servicios, pasando por aplicaciones en finanzas y teoría de la decisión, hasta aplicaciones en diagnóstico y tratamiento de enfermedades catastróficas (Montes Suay, 2007, p.95). Como punto de partida, se presentarán las Cadenas de Markov en Tiempo Discreto. Según Kulkani (2011, p.107), se definen de la siguiente forma: Cadenas de Markov en Tiempo Discreto (CMTD): un proceso estocástico en tiempo discreto {Xn,n≥0} con espacio de estado S es una CMTD si cumple que:

Esta propiedad establece que, el estado de la cadena en el paso n+1 depende exclusivamente del estado de la cadena en el paso n y es independiente del estado de la cadena en los pasos anteriores. Es decir, la propiedad se cumple solo si en el sistema a modelar. Su estado futuro depende exclusivamente del estado presente y es independiente del pasado del sistema. Si, además, la CMTD cumple que:

Entonces, la CMTD es homogénea. Utilizando la última propiedad, se establece una notación mucho más corta para las probabilidades de transición de la CMTD. Además, sin pérdida de generalidad, se asume que el espacio de estado es finito, S={1,2,…,N}, se define a:

Las probabilidades pij se conocen como probabilidades de transición de un paso. Si el espacio de estado está dado por S={1,2,…,N}, se deben calcular N2 probabilidades. Estas se pueden organizar en una matriz definida como:

POLITÉCNICO GRANCOLOMBIANO

2

La matriz P es una matriz cuadrada de tamaño N×N que cumple las siguientes propiedades

• • Cuando una matriz cuadrada cumple las dos propiedades anteriores, se dice que es una matriz estocástica.

Cómo mejorar... Una alternativa para modelar un sistema como una CMTD es la utilización de un grafo de transición de un paso. En él, cada uno de los estados se representa con un nodo mientras que las transiciones son representadas por medio de arcos. En cada uno se ubica la probabilidad de transición de un paso entre los dos nodos unidos por el arco. En la siguiente figura se ilustra la estructura del grafo.

POLITÉCNICO GRANCOLOMBIANO

3

Pij

j

Pii i

Pjk

k Pik Figura 1. Gráfico de transición de un paso Fuente: elaboración propia

Con estos elementos, ya se puede modelar un sistema, pero mientras su evolución probabilística cumpla la condición de Markov, como una CMTD. Para ello, se debe primero definir la variable de estado, teniendo presente el índice en el tiempo; luego, determinar el espacio de estados del proceso; finalmente, calcular las probabilidades de transición de un paso y construir la matriz P.

1.1. Ejemplo 1 Para ilustrar el proceso de construcción de un modelo, considere la siguiente situación (Kulkami, 2011): Una compañía tiene una máquina que cada día puede iniciar funcionando o fallando. Si al inicio de un día la máquina inició funcionando, al siguiente día iniciará funcionando con una probabilidad del 98%, sin importar lo que pasó en días anteriores. Si, por el contrario, al inicio del día, la máquina inició fallando, al siguiente día iniciará funcionando con una probabilidad del 95%, sin importar lo que pasó en los días anteriores. Una vez la máquina es reparada, queda como nueva y el ciclo inicia de nuevo.

POLITÉCNICO GRANCOLOMBIANO

4

Para modelar el sistema anterior como una CMTD, primero se debe definir la variable de estado: Xn: estado de la máquina al inicio del día n (1 si inicia funcionando, 0 si inicia fallando). Con base en la definición anterior, el espacio de estados contiene solo dos valores, por lo tanto, S={0,1}. Para calcular las probabilidades, se construye el grafo de transición que se presenta enseguida.

0,95

0,05

0,98 0

1

0,02 Figura 2. Gráfico de transición de un paso para el ejemplo Fuente: elaboración propia

De esta forma, la matriz de probabilidades de transición está dada por:

POLITÉCNICO GRANCOLOMBIANO

5

¿Sabía que...? Siempre que se tenga una matriz estocástica (matriz cuadrada con entradas mayores o iguales a cero y cuyas filas sumen 1 en todos los casos), se puede tener una CMTD que se ajuste a dicha matriz.

1.2. Ejemplo 2 Ahora, considere que la compañía adquiere una máquina idéntica a la que ya poseía; es decir, con las mismas transiciones del Ejemplo 1. Para este nuevo sistema, con dos máquinas, las cuales funcionan de forma independiente, construya una CMTD que represente la situación. Primero, para definir la variable de estado, se puede contar al inicio de cada día el número de máquinas funcionando, es decir: Xn: número de máquinas funcionando al inicio del día n.

De esta forma, el conjunto de valores que puede tomar cualquiera de las variables aleatorias definidas está formado por 0 máquinas, 1 máquina o 2 máquinas. Por lo tanto, S={0,1,2}. Después, se deben calcular las probabilidades de transición, las cuales, para el estado 0, quedan:

•

𝑝00=𝑃(𝑋1=0 |𝑋0=0)

POLITÉCNICO GRANCOLOMBIANO

6

En este caso, se tienen al inicio del día las dos máquinas fallando y se debe calcular la probabilidad de que al día siguiente las dos máquinas nuevamente inicien fallando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que cada una pase del estado fallando al estado fallando, es decir:

𝑝00=𝑃(𝑋1=0 |𝑋0=0)=(0.05)∗(0.05)=0.0025

•

𝑝01=𝑃(𝑋1=1 |𝑋0=0)

En este caso, se tienen al inicio del día las dos máquinas fallando y se debe calcular la probabilidad de que al día siguiente una de las dos máquinas inicie fallando y la otra funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que una de ellas pase del estado fallando al estado fallando y la otra del estado fallando al estado funcionando. Esto puede pasar de dos formas, porque cualquiera de las dos máquinas es la que puede pasar a funcionar, es decir:

𝑝01=𝑃(𝑋1=1 |𝑋0=0)=(0.05)∗(0.95)+ (0.95)∗(0.05)=0.095

•

𝑝02=𝑃(𝑋1=2 |𝑋0=0)

La última transición a considerar desde el estado 0 es hacia el estado 2, es decir, se tienen al inicio del día las dos máquinas fallando y se debe calcular la probabilidad de que al día siguiente las dos máquinas inicien funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que cada uno pase del estado fallando al estado funcionando, por lo tanto:

𝑝02=𝑃(𝑋1=2 |𝑋0=0)=(0.95)∗(0.95)=0.9025 Así, las transiciones desde el estado 0 forman la primera fila de la matriz de transición de un paso, las cuales se pueden representar con la siguiente figura.

POLITÉCNICO GRANCOLOMBIANO

7

0,095

1

0,0025 0

2 0,9025 Figura 3. Transiciones de un paso que parten desde el estado 0 para el ejemplo 2 Fuente: elaboración propia

Ahora, se van a considerar las transiciones que salen del estado 1.

•

𝑝10=𝑃(𝑋1=0 |𝑋0=1)

En este caso, se tienen al inicio del día una máquina fallando y una funcionando y se debe calcular la probabilidad de que al día siguiente las dos máquinas inicien fallando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que la que se encuentra fallando continúe fallando y la que está funcionando al siguiente día inicie fallando, es decir:

𝑝10=𝑃(𝑋1=0 |𝑋0=1)=(0.05)∗(0.02)=0.001

•

𝑝11=𝑃(𝑋1=1 |𝑋0=1)

POLITÉCNICO GRANCOLOMBIANO

8

En este contexto, al inicio del día se tiene una máquina fallando y una funcionando y se debe calcular la probabilidad de que al día siguiente una de las dos máquinas inicie fallando (no necesariamente la que está fallando actualmente) y la otra funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere puede ocurrir de dos formas: la primera, que la máquina que está fallando continúe fallando y que la que está funcionando continúe funcionando; la segunda, que la máquina que está fallando funcione al día siguiente y que la que está funcionando pase a fallar al siguiente día, es decir:

𝑝11=𝑃(𝑋1=1 |𝑋0=1)=(0.05)∗(0.98)+ (0.95)∗(0.02)=0.068

•

𝑝12=𝑃(𝑋1=2 |𝑋0=1)

La última transición a considerar desde el estado 1 es hacia el estado 2, es decir, se tienen al inicio del día una máquina fallando y una funcionando y se debe calcular la probabilidad de que al día siguiente las dos máquinas inicien funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que la máquina que está fallando pase al estado funcionando y que la máquina que está funcionando continúe funcionando, es decir:

𝑝12=𝑃(𝑋1=2 |𝑋0=1)=(0.95)∗(0.98)=0.931

Así, las transiciones desde el estado 1 forman la segunda fila de la matriz de transición de un paso, las cuales se pueden representar con la siguiente figura:

POLITÉCNICO GRANCOLOMBIANO

9

0,068 0,001

0

1

0,931

2 Figura 4. Transiciones de un paso que parten desde el estado 1 para el ejemplo 2 Fuente: elaboración propia

Finalmente, se deben considerar las transiciones que salen del estado 2.

•

𝑝20=𝑃(𝑋1=0 |𝑋0=2)

En este caso, se tienen al inicio del día las dos máquinas funcionando y se debe calcular la probabilidad de que al día siguiente las dos máquinas inicien fallando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que cada uno pase del estado funcionando al estado fallando, es decir:

𝑝20=𝑃(𝑋1=0 |𝑋0=2)=(0.02)∗(0.02)=0.0004

•

𝑝21=𝑃(𝑋1=1 |𝑋0=2)

POLITÉCNICO GRANCOLOMBIANO

10

Para este evento, se tienen al inicio del día las dos máquinas funcionando y se debe calcular la probabilidad de que al día siguiente una de las dos máquinas inicie fallando y la otra funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que una de ellas pase del estado funcionando al estado fallando y la otra continúe funcionando, pero eso puede pasar de dos formas, porque cualquiera de las dos máquinas es la que puede fallar, es decir:

𝑝21=𝑃(𝑋1=1 |𝑋0=2)=(0.02)∗(0.98)+ (0.98)∗(0.02)=0.0392

•

𝑝22=𝑃(𝑋1=2 |𝑋0=2)

La última transición a considerar desde el estado 2 es hacia el mismo estado 2, es decir, se tienen al inicio del día las dos máquinas funcionando y se debe calcular la probabilidad de que al día siguiente las dos máquinas continúen funcionando. Como las dos máquinas funcionan de forma independiente, lo que se requiere es que cada uno pase del estado funcionando al estado funcionando, por lo tanto:

𝑝22=𝑃(𝑋1=2 |𝑋0=2)=(0.98)∗(0.98)=0.9604

Así, las transiciones desde el estado 2 forman la última fila de la matriz de transición de un paso, las cuales se pueden representar con la siguiente figura:

POLITÉCNICO GRANCOLOMBIANO

11

1 0 0,0392

0,0004

2

0,9604 Figura 5. Transiciones de un paso que parten desde el estado 2 para el ejemplo 2 Fuente: elaboración propia

De esta forma, la matriz de probabilidades de transición está dada por:

POLITÉCNICO GRANCOLOMBIANO

12

1.3. Ejemplo 3 Como un último ejemplo, considere la siguiente situación (Ross, 2014, p.193). Suponga que el clima de Bogotá es impredecible y la lluvia aparece frecuentemente, sin embargo, la probabilidad de que un día determinado llueva depende de lo sucedido en los días anteriores. Específicamente, si ayer y hoy llovió, la probabilidad de que llueva mañana es de 0.7. Por otra parte, si hoy llovió, pero ayer no, la probabilidad de que llueva mañana es de 0.5. Además, si ayer llovió, pero hoy no, la probabilidad de que llueva mañana es de 0.4. Finalmente, si ni ayer ni hoy llovió, la probabilidad de que llueva mañana es de 0.2. Para modelar este problema, que pareciera no cumplir la propiedad de Markov, porque el clima de un día depende no solo del día anterior, sino de los dos días anteriores. Por lo tanto, se van a redefinir los estados para que cumplan con la propiedad de Markov. Considere los siguientes estados:

0. Ha llovido los dos últimos días. 1. Llovió el día anterior pero no hace dos días. 2. Llovió hace dos días, pero no el día anterior. 3. No ha llovido en los dos últimos días.

En este caso, se puede definir la variable de estado simplemente como:

Xn: estado del clima de Bogotá en el día n. Y el espacio de estados estaría dado por los estados que se acabaron de definir, es decir, S={0,1,2,3}.

POLITÉCNICO GRANCOLOMBIANO

13

Ahora, se van a calcular las probabilidades de transición de un paso, para ello primero se consideran las transiciones saliendo del estado 0. Como en este estado ha llovido los dos últimos días, digamos día 1 y día 2, se va a pasar a un estado en el cual los dos últimos días son el 2 y el 3; como el día 2 llovió, solo se puede llegar a dos estados, el estado 0 si llueve el día 3 o el estado 2 si no llueve el día 3, las otras dos probabilidades son 0. La probabilidad de que llueva el día 3, dado que en los días 1 y 2 llovió es de 0.7, mientras la probabilidad de que no llueva es de 0.3. Por lo tanto, se tiene que:

Por otra parte, si se considera el estado 1, en este estado ha llovido el último día, es decir el día 2. Como se va a pasar a un estado en el cual los dos últimos días son el 2 y el 3, como el día 2 llovió, solo se puede llegar a dos estados, el estado 0 si llueve el día 3 o el estado 2 si no llueve el día 3, las otras dos probabilidades son 0. La probabilidad de que llueva el día 3, dado que el día 1 no llovió y el día 2 sí llovió es de 0.5, la probabilidad de que no llueva el día 3 es de 0.5. Por lo tanto, se tiene que:

Si ahora se considera el estado 2, en este estado no ha llovido el último día, es decir, el día 2, se va a pasar a un estado en el cual los dos últimos días son el 2 y el 3. Como el día 2 no llovió, solo se puede llegar a dos estados, el estado 1 si llueve el día 3 o el estado 3 si no llueve el día 3, las otras dos probabilidades son 0. La probabilidad de que llueva el día 3, dado que el día 1 llovió y el día 2 no llovió es de 0.4, mientras que la probabilidad de que no llueva el día 3 es de 0.6. Por lo tanto, se tiene que:

POLITÉCNICO GRANCOLOMBIANO

14

Finalmente, si se considera el estado 3, en este estado no ha llovido en los dos últimos días, es decir los días 2 y 3, pero se va a pasar a un estado en el cual los dos últimos días son el 2 y el 3, como el día 2 no llovió, solo se puede llegar a dos estados, el estado 1 si llueve el día 3 o el estado 3 si no llueve el día 3, las otras dos probabilidades son 0. La probabilidad de que llueva el día 3, dado que los dos días anteriores no llovió es de 0.2, mientras que la probabilidad de que no llueva el día 3 es de 0.8. Por lo tanto, se tiene que:

Con estas probabilidades se puede construir la matriz de probabilidades de transición, la cual está dada por:

Con esta matriz se termina el modelo para el problema del clima de Bogotá.

POLITÉCNICO GRANCOLOMBIANO

15

En síntesis... Para modelar un sistema como una CMTD se deben seguir estos pasos: 1. Definir la variable de estado teniendo en cuenta el índice del tiempo. 2. Establecer el espacio de estados con base en la variable de estado. 3. Calcular las probabilidades de transición de un paso y construir la matriz P.

POLITÉCNICO GRANCOLOMBIANO

16

Referencias Kulkami, V. (2011). Introduction to Modeling and Analysis of Stochastic Systems. Nueva York: SpringerVerlag. Montes, F. (2007). Procesos estocásticos para ingenieros: teoría y aplicaciones. Valencia: Universidad de Valencia. Ross, S. (2014). Introduction to Probablility Models. San Diego, CA.: Academic Press.

POLITÉCNICO GRANCOLOMBIANO

17

Módulo: Programación Estocástica Unidad 2: Cadenas de Markov en tiempo discreto Escenario 3: Cadenas de Markov en tiempo discreto

Autor: Stevenson Bolívar Atuesta Asesor Pedagógico: Claudia Rocío Puentes Mendoza Diseñador Gráfico: Katherinne Pineda Rodriguez Asistente: Julieth Sthefhany Ortiz Munevar Este material pertenece al Politécnico Grancolombiano. Prohibida su reproducción total o parcial.

POLITÉCNICO GRANCOLOMBIANO

18...