Material Para Segundo Parcial

Investigación de Operaciones Material para segundo parcial

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de Markov Temario: Introducción. Proceso de Poisson. Cadenas de Markov en tiempo discreto. Clasificación de los estados y distribución límite. Cadenas de Markov en tiempo continuo.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de Markov Introducción. Un Proceso Estocástico se define como secuencia de variables aleatorias {Xt} t∈T, donde el conjunto de índices T puede ser un conjunto discreto, por ejemplo T = {0,1,2,3,...}, caso en el cual decimos que el proceso es tiempo discreto o bien T puede ser un intervalo, por ejemplo T= [0,∞ ), caso en el cual decimos que el proceso es en tiempo continuo.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de Markov Introducción. El proceso estocástico {Xt} t∈T puede representar por ejemplo: • El número de vehículos esperando en una plaza de peaje en el instante t. • El número total de llamadas recibidas solicitando un determinado servicio hasta el instante t. • El número de máquinas descompuestas o en reparación en un determinado taller en el instante t.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de Markov Introducción. • El nivel de inventario de cierto producto al final del día t. • El valor de una determinada acción en el instante t. Por ejemplo, la evolución del número de compradores en una tienda al ser abierta al público, entre las 8:00 y 9:40 de la mañana (100 minutos) puede ser representada por un proceso estocástico y una posible realización de éste se observa en la siguiente gráfica:

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de Markov Introducción.

4 Número de compradores 3 en el 2 sistema 1 0

20

40

60

Tiempo (en minutos)

80

100

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. En primer lugar, definimos un proceso estocástico de conteo {Nt} t≥ 0, que corresponde al número total de eventos o llegada de entidades, a un sistema dado, ocurridas hasta el instante t, el cual satisface: i) N0=0. ii) Los valores de Nt están restringidos a números enteros.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. iii) Nt es un proceso no decreciente en el tiempo, es decir si s < t entonces Ns ≤ Nt iv) Si s < t entonces Nt – Ns es el número total de eventos en el intervalo (s,t]

Si por ejemplo, Nt denota el número total de llamadas recibidas en una central telefónica hasta el instante t, para todo t ≥ 0, una realización posible del proceso estocástico {Nt} t≥ 0 puede ser:

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson.

6

Número de llamadas

Nt

5 4 3 2 1 0

Tiempo

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. V.2. Proceso de Poisson. Un proceso estocástico de conteo {Nt} t≥ 0 se dice un proceso de Poisson ssi satisface las siguientes propiedades: i) Incrementos estacionarios. La probabilidad de que ocurra exactamente k eventos en el intervalo (s,s+h] depende sólo del tiempo de duración h y no del instante s, es decir, si t1≥ 0, t2≥ 0 y h≥ 0 entonces Nt1+h–Nt1 y Nt2+h–Nt2 son v.a. con igual distribución.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. ii) Incrementos Independientes. El número de eventos que ocurren durante intervalos de tiempo disjuntos son independientes. Es decir, si 0
iii) Propiedad de orden. Se asume que no tiene lugar de manera simultánea la llegada u ocurrencia de dos o más eventos.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Existe una constante λ > 0 tal que para todo t ∈[0,∞ [ y h > 0, se tiene: IP(Nt+h – Nt =1) = λ h +o(h) IP(Nt+h - Nt ≥ 2) = o(h) Si {Nt}t≥ 0 es un proceso de Poisson, entonces para todo t ≥ 0, la variable aleatoria Nt es una variable aleatoria Poisson de parámetro λ t, esto es

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. IP(Nt = k) = -eλ t (λ t)k / k! ; k= 0,1,2,3,..., donde λ es la tasa de ocurrencia de eventos por unidad de tiempo. De aquí entonces que IE (Nt) = λ t Var(Nt) = λ t

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Ejemplo. Para un proceso de Poisson a tasa λ , se sabe que entre 0 y t han ocurrido n eventos. Hallar la probabilidad de que en un subintervalo de longitud h haya ocurrido exactamente k de esos eventos. Sea {Nt}t≥ 0 dicho proceso, entonces

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. IP(Nh=k / Nt=n) = IP(Nh=k, Nt=n) / IP(Nt=n) = IP(Nh=k, Nt – Nh = n - k) / IP(Nt=n) = IP(Nh=k)IP(Nt – Nh = n - k) / IP(Nt=n) = IP(Nh=k)IP(Nt-h = n - k) / IP(Nt=n) = e-λ h(λ h)k / k! e-λ e-λ t(λ t)n / n! k

 h  h   t − h  =       k  t   t 

(t-h)

n −k

(λ (t-h))n-k / (n-k)! /

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Ejemplo. Suponga que llegan pasajeros a un terminal de buses de acuerdo a un proceso de Poisson {Nt}t≥ 0 a tasa λ =3 pas./min. En el instante t=0 acaba de salir un bus y no deja ningún pasajero en la fila, suponga además que cada bus tiene una capacidad suficiente para no dejar pasajeros esperando en el terminal.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Sea T el tiempo que transcurre hasta la próxima salida de un bus, este corresponde a una v.a. uniforme en el intervalo (9 min, 11 min) y es independiente del proceso {Nt}t≥ 0. Se desea calcular el número esperado de pasajeros que aborda cada bus.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Solución 11

1 IE(Y = n) = ∫ IE(Y / T = t ) dt 11 − 9 9 11

1 = ∫ IE(Nt ) dt 2 9 1 11 = ∫ 3t dt 29 = 30

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Interesa estudiar sistemas en los cuales ocurren determinados eventos a través del tiempo. Hemos utilizado un proceso de Poisson {Nt}t≥ 0 para el número de eventos que ocurran hasta un instante t, asociado a este proceso también existen v.a. continuas T1, T2,..., Ti, ... que indican el instante de ocurrencia del i-ésimo evento y v.a. continuas S1 = T1, S2 = T2 - T1, ... que representan el tiempo transcurrido entre eventos sucesivos.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. 6 Número de eventos

Nt

5 4 3 2 1 0 T1

T2 T3

S1 S2 S3

S4

T4

T5 S5

Tiempo

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Teorema. Si {Nt}t≥ 0 es un proceso de Poisson a tasa λ , las v.a. S1, S2, S3, ... de los tiempos entre eventos sucesivos, son i.i.d. con distribución exponencial de parámetro λ . Es decir, para t≥ 0 F(t) = IP (Si ≤ t) = 1 – e-λ t

f(t) = e-λ t

son sus respectivas funciones de distribución y densidad.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Ejemplo. Sea {Nt}t≥ 0 un proceso de Poisson a tasa λ , que cuenta el número de veces que se ha reemplazado una ampolleta en una lámpara determinada. Si la primera ampolleta lleva s horas funcionando, calcular la probabilidad de que complete más de s + t horas funcionando.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Denotamos por T1 la v.a. correspondiente al tiempo transcurrido hasta que se produce el primer reemplazo. Entonces T1 ∼ Exp(λ ), luego

IP(T1 > s + t ) IP(T1 > s + t / T1 > s) = IP(T1 > s) e −λ(s+ t ) − λs = = e = IP(T1 > t ) − λt e

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Lo anterior quiere decir que el funcionamiento de la ampolleta durante las siguientes t horas no depende de cuantas horas lleva funcionando, esta propiedad es conocida como la falta de memoria de la distribución exponencial.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Ejemplo. Suponga que en un proceso productivo se tiene dos máquinas que trabajan en paralelo elaborando un mismo producto. Sean Nt1 y Nt2 procesos de Poisson independientes a tasas λ 1 y λ 2 que cuentan el número de fallas hasta el instante t de la máquina 1 y 2 respectivamente. Calcular la probabilidad de que la máquina 2 falle por primera vez antes de que la máquina 1 falle por primera vez.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Sean T1 y T2 los tiempos transcurridos hasta que se produce la primera falla en la máquina 1 y 2 respectivamente. Entonces, T1 ∼ Exp(λ 1) y T2 ∼ Exp (λ 2) y se pide calcular IP(T2
III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Condicionando el valor de T1 se tiene:

IP(T 2 ≤ T 1 ) = ∫ IP(T 2 ≤ T 1 = t )λ 1e − λ dt 1

= ∫ IP(T 2 ≤ t )λ 1e − λ t dt 1

= ∫ IP(1 − e − λ t )λ 1e − λ t dt 2

1

= 1 − λ 1 ∫ e −( λ + λ ) t dt 1

2

= 1 − λ 1 /(λ 1 + λ 2 ) = λ 2 /(λ 1 + λ 2 )

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Por otra parte, las variables aleatorias T1,T2,..., de los instantes de ocurrencia de los eventos satisfacen: T1 = S1

∼ Exp (λ )

T2 =. S1 + S2

∼ Gamma (2,λ )

. .

Ti = S1 + S2 + ... + Si ∼ Gamma (n,λ )

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Proceso de Poisson. Cuya función de distribución corresponde a: k ( λ t ) IP(Ti ≤ t ) = 1 − ∑ e − λt k! k =0 n −1

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Consideremos un ejemplo simplificado relacionado con la propagación de una enfermedad contagiosa. La transmisión de la enfermedad se produce desde un individuo infectado a uno susceptible. Consideremos periodos semanales. Sea p la probabilidad de que durante una semana cualquiera un individuo infectado le transmita la enfermedad a uno susceptible. Asuma que una vez que una persona ha sido infectada queda inmune, una vez que ha sido tratada.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Sea Xn el número de individuos susceptibles de contagio en la población, al final de la semana n=1,2,... pij = IP(X n+1 = j / X n = i) , como la Se define probabilidad de que haya j individuos susceptibles al final de la semana n+1 dado que hay exactamente i individuos susceptibles al final de la semana n (i ≥ j ).  i  i− j Entonces: pij =   p (1 − p) j  j

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Un proceso estocástico en tiempo discreto {Xn}n=1,2,.... se denomina una Cadena de Markov en tiempo discreto ssi satisface las siguientes propiedades: i) Propiedad Markoviana:

IP(X n+1 = j / X 0 = i0 , X 1 = i1,..., X n−1 = in−1, X n = i) = IP(X n+1 = j / X n = i) Donde i0, i1, ..., in-1, i, j son posibles “ estados” o valores que puede tomar el proceso estocástico en las distintas etapas.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. ii) Propiedad estacionaria: pij = IP(X n+1 = j / X n = i) , no La probabilidad depende de la etapa n. Las probabilidades pij son llamadas “probabilidades de transición en una etapa del estado i al estado j “. Suponiendo que cada etapa n la v.a. Xn toma un número finito de valores (estados), digamos 1,2,... M; estas probabilidades definen una matriz P de probabilidades de transición en una etapa.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto.

P = (pij )i=1...M

j=1...M

p12  p11  p p 22  21 = p  (M−1)1 p (M−1)2  pM1 p M2

⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅

p1M  p 2M     p (M−1)M  pMM 

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Adicionalmente, se supone conocida la distribución de probabilidad de la Cadena de Markov en la etapa inicial, que denotamos según f0 , donde :

 IP(X 0 = 1)   IP(X = 2)  0  f0 =    IP(X = M)   0

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. El conocimiento del proceso estocástico {Xn}n=0,1,2,...consiste en poder determinar la distribución de probabilidad en cada etapa, esto es calcular IP (Xn = j) para cada n ≥ 1 y estado j= 1,2,.....,M. Notar que para cada j:

IP(X n = j) = ∑ IP(X n = j / X n−1 = i) IP(X n−1 = i) i

= ∑ pij IP(X n−1 = i) i

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Matricialmente esto equivale a tener:  IP(X n = 1)   p11 p 21 ⋅ ⋅ pM1   IP(X = 2)  p  p ⋅ ⋅ p n 12 22 M2     fn =  =          IP(X n = M) p1M p 2M ⋅ ⋅ pMM  De manera recursiva se tiene entonces: fn = PT fn-1 = (PT)n f0

 IP(X n−1 = 1)   IP(X  = 2 ) n −1         IP(X n−1 = M)

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. También es posible obtener las probabilidades de transición de un estado a otro al cabo de k etapas, que denotamos por :

pij(k ) = IP(X n+k = j / X n = i) = IP(X k = j / X 0 = i) Que resumidas en una matriz ( para el caso de un número finito de estados).

P (k ) = (pij(k ) ) Estas satisfacen las ecuaciones de Chapman y Kolmogorov que implican: P(k) = Pk

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Ejemplo 1. Considere una tienda que mantiene un inventario de un producto dado para satisfacer una demanda (aleatoria). La demanda diaria D, tiene la siguiente distribución: IP (D = 0) = 1/4, IP (D = 1) = 1/2, IP (D = 2) = 1/4, IP (D >= 3) = 0 Sea Xn el nivel de inventario al inicio del día n y suponga que la tienda tiene la política de mantención de inventario (s, S), que consiste en que si al final del día se posee menos de s, se

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. hace una orden de pedido que al inicio del día siguiente eleva las existencias al nivel S y en caso contrario, no se pide nada. Asuma que la demanda no satisfecha es demanda perdida y que al inicio del horizonte de planificación hay S unidades en inventario con s = 1 y S = 2. Se tiene que: Xn ∈ {1, 2} ; n = 0, 1, 2, ...

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto.

 IP(x 0 = 1)  0 f = =   IP(x 0 = 2)  1 pi, j = IP(X n+1 = j / X n = i) 0

; i, j ∈ {1,2}

p11 = IP(D = 0) = 1/ 4 p12 = IP(D ≥ 1) = 3 / 4 p 21 = IP(D = 1) = 1/ 2 p 22 = IP(D = 0) + IP(D ≥ 2) = 1/ 2

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Entonces la matriz de probabilidades de transición en una etapa corresponde a:

1/ 4 3 / 4  P=  1 / 2 1 / 2  

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Ejemplo 2. Suponga que en el sistema de las AFP existen solo 2; las AFP A y las AFP B. Sea N el número de personas afiliadas al sistema; la superintendencia está preocupada de que las cuentas individuales estén al día. Para ello ha establecido un sistema de control basado en el siguiente procedimiento: al final de cada mes escoge una persona al azar de los N existentes en el sistema.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Si la AFP a la cual pertenece la persona no tiene su cuenta individual al día; la persona es traspasada de inmediato a la otra AFP, en caso contrario la deja en la AFP en la que estaba. Suponga que la probabilidad de que un afiliado en la AFP A tenga su cuenta al día es P1 y que esta probabilidad para la AFP B es P2. Se desea estudiar la movilidad de los clientes en cada AFP en cada mes del horizonte de planificación.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto. Se tiene: Xn: el número de personas en la AFP A al final del mes n; con n = 0, 1, 2, ..., n xn ∈ {0, 1, 2, ..., N} Calculemos las probabilidades de transición en una etapa (mes)

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo discreto.

i pi,i−1 = (1 − P1 ) ; 1 ≤ i ≤ N − 1 N i (N − i) pi,i = P1 + P2 N N (N − i) pi,i+1 = (1 − P2 ) N pij = 0 ; j ≠ i − 1, i, i + 1 p 0,0 = P2

p 0,1 = (1 − P2 )

pN,N−1 = 1 − P1

pN,N = P1

p 0, j = 0 j ≠ 0,1 pNj = 0 j ≠ N − 1, N

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los estados y distribución límite. En esta sección se presentan algunos resultados que tienen relación con la existencia y cálculo de una distribución para la Cadena de Markov en el largo plazo. Previamente, se enumeran algunas definiciones que clasifican los estados de una cadena: i) Un estado j se dice accesible desde el estado i ssi para algún n

pij(n) = IP(X n = j / X 0 = i) > 0

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. ii) Si tanto el estado i es accesible desde j como viceversa decimos que los estados i y j se comunican. iii) Dos estados que se comunican están en una misma clase de estados. iv) Se dice que una cadena es irreducible si hay una sola clase de estados.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. v) Un estado se dice que tiene periodo d, para el mayor valor del entero d que cumple:

pii(n) = IP(X n = i / X 0 = i) > 0 sólo para valores de n pertenecientes al conjunto {d, 2d, 3d, ....}. Si d=1 decimos que el estado es aperiódico.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. vi) Se define T(i,j) como el número de etapas requeridas por el proceso para pasar de estado i al estado j por primera vez. De igual modo se define:

Fk (i, j) = IP(T (i, j) = k ) es decir :

Fk (i, j) = IP(X k = j, X k −1 ≠ j,..., X 1 ≠ j / X 0 = i) como la probabilidad de que comenzando en i, ocurra la primera transición al estado j al cabo de exactamente k etapas.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Puede probarse por inducción, la siguiente formula: F1(i, j) = pij

Fk = (i, j) = ∑ pim Fk −1(m, j), m≠ j

k >1

vii) En particular, se denota por Fk(i,i) la probabilidad de que el proceso retorne al estado i por primera vez al cabo de k etapas. De modo que:

F(i, i) =

∞

∑ Fk (i,i)

k =1

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. que es la probabilidad que partiendo en i , el proceso regrese al estado i alguna vez. viii) Un estado se dice recurrente ssi F(i,i) = 1 ix) Un estado se dice transciente ssi F(i,i)< 1 ∞ IE ( T ( i , i )) = ∑k =1k Fk (i, i) x) Sea , el valor esperado de el número de etapas que le toma al proceso volver al estado i por primera vez, partiendo del estado i.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Un estado se dice recurrente positivo ssi:

F(i, i) = 1 y

IE(T (i, i)) < +∞

Un estado se dice recurrente nulo ssi :

F(i, i) = 1 y

IE(T (i, i)) = +∞

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Ejemplo

0  1/ 2 1/ 2 p =  0 1/ 3 2 / 3   1/ 3 1/ 3 1/ 3 

Define una cadena de estados irreducible con estados recurrente positivos periódicos

0   1 1/ 2 p = 1/ 2 1/ 6 1/ 3    1/ 5 3 / 5 1/ 5 

Posee dos clases de estados y uno de los estados es transciente.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite.

 0 1/ 2 p=  0  1 

1 0 0 1/ 2 0 0 0 0

0 0  1 0

Es una cadena irreducible, de estados recurrentes positivos y todos sus estados son periódicos de periodo d=2.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Si la distribución de probabilidad del proceso en el largo plazo existe y es independiente de la distribución inicial (o del estado inicial), decimos que el proceso tiene una distribución estacionaria

π

= ( π 1, π 2, ..., π M) T

π j = lim IP(X n = j) = lim pij(n) n→ ∞

n→∞

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Proposición. Sea {Xn}n=0,1,2 una cadena de Markov irreducible con estados recurrentes positivos aperiódicos, entonces existe una distribución estacionaria π , tal que π > 0 y que se obtiene como la solución única del sistema: π = PT π ∑ πj = 1 j

πj ≥ 0

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Ejemplo. Se desea calcular las probabilidades estacionaria π j, que también representan la fracción del tiempo que el sistema esta en el estado j en el largo plazo 1/2 1/2

0  1/ 2 1/ 2 p =  0 1/ 3 2 / 3   1/ 3 1/ 3 1/ 3 

1 1/3 1/3

T

π=P π π1 + π 2 + π 3 = 1

3 1/3

2

2/3

1/3

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Sistema que ecuaciones:

(1) (2) (3) (4)

corresponde

a

las

1 1 π1 + π 3 2 3 1 1 1 π2 = π1 + π2 + π3 2 3 3 2 1 π3 = π2 + π3 3 3 π1 + π2 + π3 = 1

π1 =

siguientes

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite.

de de

2 (1) π1 = π3 3 (2) π2 = π3

2 así π3 + π3 + π3 = 1 3 1 3 ∴ Solución π1 = π2 = π3 = 4 8

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Ejemplo: Una compañía esta considerando emplear cadenas de markov para analizar los cambios en las preferencias de los usuarios por tres marcas distintas de un determinado producto. El estudio ha arrojado la siguiente estimación de la matriz de probabilidades de cambiarse de una marca a otra cada mes: 1 2 3 1

0.8

0.1

0.1

2

0.03

0.95

0.02

3

0.2

0.05

0.75

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. En la actualidad los porcentajes de mercado son 45%, 25% y 30%, respectivamente. ¿Cuales serán los porcentajes de mercado de cada marca en dos meses más? xn ∈{1,2,3}: marca que adquiere un cliente cualquiera en el mes n=0,1,2,3,...

 IP(X 0 = 1) = 0.45  f 0 = IP(X 0 = 2) = 0.25    IP(X 0 = 3) = 0.30 

0.1 0.1   0 .8 P = 0.03 0.95 0.02     0.2 0.05 0.75 

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. Al término del mes siguiente:  IP(X 1 = 1) = 0.4275  f 1 = P T f 0 = IP(X 1 = 2) = 0.2975    IP(X 1 = 3) = 0.2750  Y dos meses después:  IP(X 2 = 1) = 0.4059  f 2 = P T f 1 =  IP(X 2 = 2) = 0.3391   IP(X 2 = 3) = 0.2550 

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. De aquí las cuotas de mercado en dos meses a cambiado de un 45% a un 40.59%; de un 25% a un 33.91% y de un 30% a un 25.50%, para las marcas 1,2 y 3 respectivamente. ¿Cuál es la cuota de mercado en el largo plazo para cada una de las marcas? La cadena resultante es irreducible con estados recurrentes positivos y aperiódicos . Denotando por π =(π 1, π 2, π 3)T, las probabilidades estacionarias de largo plazo, las cuales satisfacen:

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. π =PT π Σ π i=1;

i = 1,2,3.

π 1=0.8 π 1+ 0.03 π 2+0.20 π π 2=0.10 π 1+ 0.95 π 2+0.05 π π 3=0.10 π 1+ 0.02 π 2+0.75 π π 1 + π 2+ π 3 =1 Cuya solución resulta: π 1= 0.2373 π 2= 0.6184

3 3 3

π 3= 0.1443

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Clasificación de los est. y distribución límite. De aquí que la cuotas de mercado en el largo plazo resultan ser 23.73%, 61.84% y 14.43% para las marcas 1,2 y 3 respectivamente. Notar que las actuales cuotas difieren significativamente de las cuotas obtenidas en el largo plazo lo cual puede implicar que de alguna manera deban ser corregidas las probabilidades de transición.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo.

Se desea estudiar el comportamiento de sistemas que dependen en forma continua del tiempo: Xt: número de ambulancias disponibles en el instante t. Xt: número de personas esperando ser atendidas en el banco o en el supermercado en el instante t. Xt: número de máquinas funcionando correctamente en un taller en el instante t.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Propiedad Markoviana:

IP(X t + s = j / X u = X(u), 0 ≤ u ≤ t, X t = i) = IP(X t + s = j / X t = i) Propiedad Estacionaria

IP(X t + s = j / X t = i) , no depende de t, sólo de s.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Una realización posible del proceso estocástico es:

4 3

Xt

2 1

t

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. ¿Cómo representar el proceso? - Se necesitan las probabilidades de que ocurra un “salto” de un estado a otro. - La distribución de los tiempos de permanencia en un estado. Se necesita explicitar: i) Probabilidades de transición pij (asumiendo pii=0) ii) Tasas vi de los tiempos exponenciales Ti de permanencia en el estado i.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Distribución de Xt :

pij (t ) = IP(X t = j / X 0 = i) Estas probabilidades satisfacen:

d pij (t ) = ∑ pik (t )vkpkj − v jpij (t ) dt k≠ j Si existe una distribución estacionaria: π j = lim pij (t ) t →∞

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. La ecuación diferencial anterior provee el siguiente sistema de ecuaciones para las probabilidades estacionarias (de existir):

0=

∑ πk vkpkj − v jπ j ; j = 1,2,...

∑ πj = 1

k≠ j

j

O equivalentemente el sistema:

v jπ j =

∑ πk vkpkj ; j = 1,2,...

k≠ j

∑ πj = 1 j

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Ejemplo : En el puerto de Valparaíso existen N trenes encargados de traer cargas de contenedores desde los buques hasta una unidad de descarga. En esta unidad existen c grúas ( c < N) para descargar los trenes. El tiempo que le toma a una grúa descargar un tren es exponencial a tasa µ . Un tren deja la unidad de descarga cuando la grúa termina de atenderlo y vuelve con una nueva carga después de un tiempo exponencial de tasa λ . Formular un modelo que nos permita obtener en el largo plazo :

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. - Número medio de trenes esperando ser atendidos en la cuidad de descarga - Número medio de grúas que se encuentran atendiendo trenes Fracción del tiempo en que hay al menos una grúya desocupada Xt : El número de trenes que están en la unidad de descarga (Xt ∈{0,1,2,...,N}) Si existen 0 ≤ j ≤ c trenes en la unidad de descarga vj= j µ + (N – j) λ

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Es decir, el tiempo que transcurre con j trenes en la unidad de descarga es una v.a. Exponencial correspondiente al mínimo entre los tiempos que transcurren hasta que se descarga completamente un tren de los j existentes en dicha unidad y los tiempos que transcurren hasta que retorna uno de N – j trenes que vuelve con carga.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Además, las únicas posibles transiciones son: pj,j-1= j µ / (j µ + (N – j ) λ )

j>0

pj,j+1=( N- j ) λ / (j µ + (N – j ) λ ) Esto es, las probabilidades que se termine de descargar un tren antes de que vuelva uno con carga y viceversa.

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Análogamente si c < j ≤ N resultan:

estos parámetros

vj= c µ + (N – j) λ pj,j-1= c µ / (cµ + (N – j ) λ ) pj,j+1=( N - j ) λ / (cµ + (N – j ) λ )

(j≤ N)

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. En este caso las ecuaciones que determinan las probabilidades estacionarias : Resultan ser las siguientes:

π j = lim pij (t )

Nλ π 0 = [µ + ( N – 1 )] =Nλ π 0 ... [cµ + ( N – c ) λ ] π C = (N –( c – 1)) λ π ... [cµ + λ ] π N-1 = 2 λ π N-2

t →∞

µ π 1 +2µ π c-1

2

+cµ π

C+1

+cµ π

N

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. c µ π N= λ π π 1+ π 1+...+ π

N

N-1

=1

Así, el número de trenes esperando ser atendidos en la unidad de descarga es : N ∑ (n − c) πn n=c

El número promedio de grúas atendiendo trenes c N ∑ n πn + ∑ c πn n =1

n = c +1

III. Modelos Probabilísticos Ptrocesos Estocásticos y Cadenas de MarkoIII. Cadenas de Markov en tiempo continuo. Y la fracción de tiempo en que hay al menos una grúa desocupada es : c −1

∑ πn

n=0