Unidad 4 Cadenas DE Markov PDF

Preview

Summary

cadenas de Markov...

Description

Investigación de operación II. Investigación unidad 4 Cadenas de Markov. ING. Miguel Estrada Cardiel. Alumno: Pedro Manuel Barron Calderilla. ING. Industrial 6to cuatrimestre.

04/08/20

1

ÍNDICE INTRODUCCIÓN…………………………………………………………………….3

4.1. INTRODUCCIÓN A LAS CADENAS DE MARKOV………………………...6

4.2. PROBABILIDAD DE TRANSICIONES ESTACIONARIAS DE N PASOS…8

4.3. ESTADO ESTABLE……………………………………………………………10 4.4. ESTADOS ABSORBENTES…………………………………………………..12 4.5. USO DE SOFTWARE CONCLUSIÓN………………………………………………………………………..14 BIBLIOGRAFIA……………………………………………………………………….14

2

INTRODUCCIÓN En las cadenas de Markov considera ciertos puntos discretos en el tiempo, para toma valores de 1, 2, 3,…. Y la variable aleatoria que caracteriza al sistema. Y la familia de las variables aleatorias forma un proceso llamado proceso estocástico. Entonces las cadenas de Markov se usan para estudiar ciertos comportamientos de largo y cortos plazos de sistemas estocásticos. Para un proceso de Markov es un sistema estocástico siempre que cumpla con la propiedad Markoviana. Los estados en el tiempo representan situación exhaustiva y mutuamente excluyentes del sistema en un tiempo específico. Además el número de estado puede ser finito o infinito. Un ejemplo es el juego delanzar la moneda. Por lo general una cadena de Markov describe el comportamiento de transición de un sistema en intervalos de tiempo igualmente espaciados. Sin embargo, existen situaciones donde los espaciamientos temporales dependen de las características del sistema y por ello, pueden no ser iguales entre sí. Estos casos se denominan cadenas de Markov incrustadas. Con las probabilidades absolutas y de transición podremos hacer predicciones de comportamientos futuros como las que se observaron en las situaciones anteriores. Así, si llamamos estados a cada una de estas posibilidades que se pueden presentar en un experimento o situación específica, entonces podemos visualizar en las Cadenas de Markov una herramienta que nos permitiría conocer a corto y largo plazo los estados en que se encontrarían en periodos o tiempos futuros y tomar decisiones que afectarán o favorecerán nuestros intereses. Las probabilidades absolutas y de transición son exhaustivas y mutuamente excluyentes de un experimento aleatorio en cualquier tiempo. 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. Las cadenas de Markov se pueden aplicar en áreas como la educación, comercialización, servicios

3

Formulación de las cadenas de Markov. En la figura 4.1 se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, Ej , donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no tienen que ser iguales ). Las probabilidades de ocurrencia para cada uno de estos eventos depende del estado del generador. Este estado se describe por el último evento generado. En la figura 4.1, el último evento generado fue Ej , de manera que el generador se encuentra en el estado Mj .

La probabilidad de que E k sea el siguiente evento generado es una probabilidad condicional : P ( Ek / Mj ). Esto se llama probabilidad de transición del estado M j al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición. Probabilidades de transición. Una forma de describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 4.2. En ésta se ilustra un sistema de Markov con cuatro estados posibles : M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama.

4

Otro método para exhibir las probabilidades de transición es usar una matriz de transición. . La matriz de transición para el ejemplo del diagrama de estados se muestra en la tabla 4.1 .

Otra forma de exhibir las probabilidades de transición es, para n = 0, 1, 2, .... ,:

El superíndice n no se escribe cuando n = 1.

Procesos estocásticos. Un proceso estocástico se define sencillamente como una colección indexada de variables aleatorias { Xt }, donde el subíndice t toma valores de un conjunto T dado. Con frecuencia T se toma como el conjunto de enteros no negativos, y X representa una característica de interés medible en el tiempo t. Por ejemplo, el proceso estocástico, X1 , X2 , X3, .., puede representar la colección de niveles de inventario semanales (o mensuales) de un producto dado, o puede representar la colección de demandas semanales (o mensuales) de este producto.

Un estudio del comportamiento de un sistema de operación durante algún periodo suele llevar al análisis de un proceso estocástico con la siguiente estructura. En puntos específicos del tiempo t , el sistema se encuentra exactamente en una de un número finito de estados mutuamente excluyentes y exhaustivos, etiquetados 0, 1, . . , s. Los periodos en el tiempo pueden encontrarse a intervalos iguales o su esparcimiento puede depender del comportamiento general del sistema en el que se encuentra sumergido el proceso estocástico. Aunque los estados pueden constituir una caracterización tanto cualitativa como cuantitativa del sistema, no hay pérdida de generalidad con las etiquetas numéricas 0, 1, . . , M , que se usarán en adelante para denotar los estados posibles del sistema. De esta forma, la representación matemática del sistema físico es la de un proceso estocástico {Xi}, en donde las variables aleatorias se observan en t = 0, 1, 2,. . ., y en donde cada variable aleatoria puede tomar el valor de cualquiera de los M + 1 enteros 0, 1, .. , M . Estos enteros son una caracterización de los M + 1 estados del proceso. Propiedad Markoviana de primer orden. Se dice que un proceso estocástico tiene la propiedad markoviana si P { Xt+1 = j | X0 = K0 , X1 = K1 , . ., Xt-1 = Kt-1 , = Kt-1, Xt = 1} = P { X t+1 | X1 = i }, para toda t = 0, 1, . . y toda sucesión i, j , K0 , K1 , . . , Ki-1 . Se puede demostrar que esta propiedad markoviana es equivalente a establecer una probabilidad condicional de cualquier "evento" futuro dados cualquier "evento " pasado y el estado actual Xi = i , es independiente del evento pasado y sólo depende del estado actual del proceso. Las probabilidades condicionales P{ X t+1 = j | Xt = i } se llaman probabilidades de transición. Si para cada i y j, P{ X t+1 = j | | Xt = i } = p{ X1 = j | X0 = i }, para toda t = 0, 1, .... Entonces se dice que las probabilidades de transición (de un paso) son estacionarias y por lo general se denotan por pij . Así, tener probabilidades de transición estacionarias implican que las probabilidades de transición no cambian con el tiempo. La existencia de probabilidades de transición (de un paso) estacionarias también implica que, para cada i, j y n (n = 0, 1, 2,...), P{ Xt+n = j | | Xt = i } = p{Xn = j | X0 = i }, Para toda t = 0, 1, . . . Estas probabilidades condicionales casi siempre se denotan por

y

se

llaman probabilidades de transición de n pasos. De esta manera, es simplemente la probabilidad condicional de que la variable aleatoria X, comenzando en el estado i, se encuentre en el estado j después de n pasos ( unidades de tiempo ).

Como las

son probabilidades condicionales, deben satisfacer las propiedades:

Probabilidad de transición de un solo paso. Ejemplo : Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, ...Dn las demandas de esta cámara durante la primera semana, segunda semana, n-ésima semana, respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3. El sábado en la tarde la tienda hace un pedido que le entregan el lunes al momento de abrir. La tienda usa la siguiente política ( s, S) para ordenar : si el número de cámaras en inventario al final de la semana es menor que s = 1 (no hay cámaras en la tienda), ordenar S = 3. De otra manera, no coloca la orden (si se cuenta con una o más cámaras en el almacén, no se hace el pedido). Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, { Xt } para t = 0, 1, ..n es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3, que representan el número posible de cámaras en inventario al final de la semana. Se observa que {Xi } ( en donde Xi es el número de cámaras en el almacén al final de la semana i antes de recibir el pedido ), es una cadena de Markov. Se ve ahora cómo obtener las probabilidades de transición (de un paso), es decir, los elementos de la matriz de transición ( de un paso), Suponiendo que cada Dt tiene una distribución Poisson con parámetro  = 1. P0 P P0 P0 P1 P P1 P1 p P2 P P2 P2 = P3 P P3 P3 Las probabilidades de Poisson para  = 1 y diferentes valores de demanda son: D p(

0 0.3

1 0.7

2 0.9

3 0.9

4 0.9

5 0.9

6 1.0

Para obtener P00 es necesario evaluar P Xt = 0  Xt-1 = 0 . Si Xt-1 = 0, entonces Xt = máx.  (3  Dt , 0 . Por lo tanto Xt = 0 significa que la demanda durante la semana fue de tres o más cámaras. Así, P00 = P Dt ≥ 3  = 1  P Dt ≤ 2  = 1  0.920 = 0.080, es la probabilidad de que una variable aleatoria Poisson con parámetro  = 1 tome el valor de 3 o más. De manera similar se obtiene P10 como P10 = P Xt = 0  Xt-1 = 1  . Si Xt-1 = 1, entonces Xt = máx.  (1  Dt , 0 . Para obtener Xt = 0, la demanda durante la semana debe ser 1 o más. Por esto, P10 = P Dt ≥ 1  = 1  P Dt = 0  = 1  0.368 = 0.632. Para encontrar P21 = P Xt = 1  Xt-1 = 2 . Si Xt-1 = 2 y Xt = máx.  (2  Dt , 0 , en consecuencia Xt = 1; entonces la demanda durante la semana tiene que ser exactamente 1, y la probabilidad debe ser de menos de 1. Esto significa que P21 = P Dt ≤ 1  = P Dt = 0 = 0.368. Los elementos restantes se obtienen en forma similar, lo que lleva a la siguiente matriz de transición (de un paso): 0 1 2 3

0 1 – p(2) = . 1 – p(0) = . 1 – p(1) = . 1 – p(2) = .

1 (1 – p(1)) – (1 – p(2)) = p(0) = 0.368 (1 – p(0)) – (1 – p(1)) = (1 – p(1)) – (1 – p(2)) =

2 (1 – p(0)) – (1 – p(1)) = 0 p(0) = 0.368 (1 – p(0)) – (1 – p(1)) =

3 p(0) = 0 0 p(0) =

Probabilidad de transición estacionaria de 1 paso. p 0 . . . .

0 1 2 3

1 . . . .

2 . 0 . .

3 . 0 0 .

Las ecuaciones de Chapman-Kolmogorov proporcionan un método para calcular estas probabilidades de transición de n pasos: (

)

∑

(

)

(

)

Estas ecuaciones simplemente señalan que al ir de un estado i al estado j en n pasos, el proceso estará en algún estado k después de exactamente m ( menor que n) pasos. Así, es solo la probabilidad condicional de que, si se comienza en el estado i, el proceso vaya al estado k después de m pasos y después al estado j en n- m pasos Los casos especiales de m=1 y m= n-1 conducen a las expresiones: ( )

∑

( )

(

∑

)

y

( )

(

)

para toda i, j, y n, de lo cual resulta que las probabilidades de transición de n pasos se pueden obtener a partir de las probabilidades de transición de un paso de manera recursiva. Para n=2, estas expresiones se vuelven :

( )

Note que las

∑

son los elementos de la matriz P(2) ,pero también debe observarse

( )

que estos elementos ∑

se obtienen multiplicando la matriz de transición de un paso por sí misma; esto es , p = p * p = p2 . En términos más generales se concluye que la matriz de probabilidades de transi(n) n n-1 n-1 ción de n pasos se puede obtener de la expresión : p = p * p .... p = p = pp = p p. Entonces, la matriz de probabilidades de transición de n pasos se puede obtener calculando la n-ésima potencia de la matriz de transición de un paso. Para valores no muy grandes de n, la matriz de transición de n pasos se puede calcular en la forma que se acaba de describir, pero cuando n es grande, tales cálculos resultan tediosos y, más aún, los errores de redondeo pueden causar inexactitudes. (2)

Ejemplo : Retomando el ejemplo de las cámaras, para p(2) = p2, se tiene: p 0 1 2 3

0 . . . .

1 . . . .

* 2 . 0 . .

3 . 0 0 .

p

*

0 . . . .

1 . . . .

p2

= 2 . 0 . .

3 . 0 0 .

=

0 . . . .

1 . . . .

2 . . . .

3 . . . .

Así, dado que se tiene una cámara al final de una semana, la probabilidad de que ( ) no haya cámaras en inventario dos semanas después es 0.283; es decir, . De igual manera, dado que se tienen dos cámaras al final de una semana, la probabilidad de que haya tres cámaras en el almacén dos semanas después es 0.097; esto es,

( )

La matriz de transición de cuatro pasos también puede obtenerse como: p(4) = p4 = p(2) * p(2) p(2) 0 1 2 3

0 . . . .

1 . . . .

p(2)

* 2 . . . .

3 . . . .

*

0 . . . .

1 . . . .

2 . . . .

p(4)

= 3 . . . .

=

0 . . . .

1 . . . .

2 . . . .

3 . . . .

Así, dado que queda una cámara al final de una semana, 0.282 es( la probabilidad ) de que no haya cámaras en inventario 4 semanas más tarde; es decir,

De igual manera, dado que quedan dos cámaras en el almacén final de una semana, se tiene una probabilidad de 0.171 de que haya tres cámaras en el almacén 4 ( ) semanas después; esto es, Probabilidades de transición estacionaria de estados estables. Teorema Sea P la matriz de transición de una cadena de M estados . Existe entonces un vector

tal que

Se establece que para cualquier estado inicial i ,

.

El vector a menudo se llama distribución de estado estable, o también distribución de equilibrio para la cadena de Markov. Para encontrar la distribución de probabilidades de estacionario para una cadena dada cuya matriz de transición es P, según el teorema, para n grande y para toda i , (1) n Como Pij (n + 1) = ( renglón i de P )(columna j de P), podemos escribir (2)

Ejemplo : Suponga que toda la industria de refrescos produce dos refrescos , A y B. Cuando una persona ha comprado el refresco A, hay una probabilidad de 90 % de que su siguiente compra sea de refresco A. Si una persona compró refresco B, hay un 80 % de probabilidades que su próxima compra sea de refresco B. Compra 1 Refresco A Refresco B

Compra 2 Refresco Refresco 90% 10% 20% 80%

p=

pAA

pAB

pBA

pBB

=

.90

.10

.20

.80

Entonces : 1

=

1

2

.90 .20

. 1.



1 2

.90 1 + .20 .10 1 + .80 

De la condición 1 + 2 = 1,  1 = 1 - 2. Al reemplazar esta expresión en la segunda ecuación, se tiene: 2 = .10(1  2) + .80 2 2 = .10  .10 2 + .80 2 2 = .10 + .70 2 2  .70 2 = .10 .30 2 = .10  2 = ⅓ De la primera ecuación: 1 = .90 1 + .20 2 1 = .90 1 + .20 (⅓) 1  .90 1 = .20 (⅓) .10 1 = .20 (⅓) 1 = .20 (⅓) .10  1 = ⅔ Esto significa que, después de largo tiempo, hay ⅔ de probabilidad de que una persona compre refresco A y ⅓ de probabilidad de que una persona compre refresco B. Ejemplo : Cierta compañía se especializa en el arrendamiento de camiones a personas que desean realizar sus propias mudanzas. El gerente de distribución de la compañía está considerando la posibilidad de aplicar un “cargo por traslado” para cubrir el costo de enviar camiones desde áreas en las que hay sobrantes a otras en las que se necesitan. Antes de decidir si se debe aplicar el cargo por traslado al costo de arrendamiento de los camiones que se dirigen a áreas en las que hay sobrantes, desea determinar la proporción del número total de camiones que, a largo plazo, acabarán en cada una de las áreas de renta. Si las proporciones son aproximadamente las mismas, el cargo por traslado será innecesario. Si no es así, el cargo dependerá de la proporción del total que termine en cada región. El gerente de distribución ha dividido la parte del país que atiende la compañía en tres regiones: norte, centro y sur. De registros previos se ha determinado la siguiente información, referente a la proporción de camiones que se rentan en determinada región y dónde se entregan: Región donde se Nort e Cent M.C. José Alberto estrada Beltrán

Región donde se Nort Centr 20% 30% 30% 40% 20% 40%

Sur 50% 30% 40% 8

En este momento 40% de los camiones están en el norte, 30% en el centro y 30% en la región sur. Dado el patrón de movimiento de los camiones, la compañía está interesada en saber lo siguiente: 1. ¿ Qué proporción de camiones se encontrará en cada región después de un mes ? ¿ Después de dos meses ? 2. Qué proporción de los camiones estará en cada región en un período “largo” ? DIAGRAMA DE ÁRBOL Ubicación en el mes 0

Ubicación en el mes 1

Ubicación en el mes 2

Probabilidad de cada ubicación el mes 2

Norte

0.04

Centro

0.06

Sur

0.10

Norte

0.09

0.2 0.3 Norte 0.5 0.2 Norte0.3 0.3Centro

0.5

0.4 Centro

0.12

0.3

Sur

0.09

Norte

0.10

0.2 0.4 Centro 0.20 Sur 0.4 Sur 0.20 La probabilidad de estar en el norte en cada uno de los tres meses (mes 0, 1 y 2) está dada por: ( 0.2 ) * ( 0.2 ) = 0.04 Para determinar la probabilidad de que un camión se encuentre en el norte después de dos meses, se suman las tres probabilidades de encontrarlo en el norte: p ( estar en el norte dado que se encontraba en el norte en el mes 0 ) = 0.04 + 0.09 + 0.10 = 0.23 p ( estar en el centro dado que se encontraba en el norte en el mes 0 ) = 0.06 + 0.12 + 0.20 = 0.38 p ( estar en el sur dado que se encontraba en el norte en el mes 0 ) = 0.10 + 0.09 + 0.20 = 0.39 9

Utilizando notación matricial, los cálculos para el mes 1 son: N C S N C S N 0 0. 0 N C S 1 0 0 * CS 0 0 0. 0. 0. =0. 0 0. 0 Vector de probabilidad Matriz de transición Vector de probabilidad para comenzar en el de un mes después de un mes norte Para el segundo mes, los cálculos son: N C S N C S N 0 N C S 0. 0. * C S 0. 0. 0. 0 0. 0.2 0.3 0.3 =0. 0 0. 0. Vector de probabilidad Matriz de transición Vector de probabilidad Después de un mes de un mes después de dos meses

N 1

Estos mismos cálculos se pueden obtener de la siguiente manera: N C S N CS N 0 C S N N 0 0. 0 0 0 0 0 *CS 0 0. 0 * C 0 0 0 = 0.2 0 0. 0 S 0 0 0

Vector de probabilidad para en el norte

Matriz de transición de un mes

Matriz de transición de un mes

C 0.3

S 0.3

Vector de dad después de meses

Para calcular la proporción de camiones que se encontrarán en cada región después de dos meses, solo se sustituye la porción original ...