• Author / Uploaded
• Nicolas Gomez

• Categories
• Cadena Markov
• Matriz (Matemáticas)
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas

Citation preview

Cadenas de Markov en Tiempo Discreto Fabi´an Mancilla U. de Santiago de Chile [email protected]

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

1 / 32

Cadenas de Markov En esta unidad consideraremos procesos estoc´asticos de tiempo y estados discretos. Es decir, procesos del tipo {Xn ; n ∈ N} donde Xn corresponden a variables aleatorias discretas. Un ejemplo de este tipo de proceso es el lanzamiento de una moneda repetidas veces; Xk representa el resultado de la moneda en el k-´esimo lanzamiento, en donde el espacio muestral es ΩXk = {cara, sello} = {0, 1}.

Propiedad markoviana Se dice que el proceso {Xn ; n ∈ N} cumple con la propiedad markoviana de primer orden si P (Xn+1 = j/Xn = i, Xn−1 = in−1 , . . . , X1 = i1 , X0 = i0 ) = pij donde pij = P (Xn+1 = j/Xn = i) se denomina probabilidad de transici´on en una etapa. Esta propiedad describe la falta de memoria de un proceso. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

2 / 32

Cadenas de Markov

Propiedad de estacionariedad El proceso {Xn ; n ∈ N} cumple con la propiedad de estacionariedad si la probabilidad de transici´on en una etapa pij = P (Xn+1 = j/Xn = i) depende s´ olo de i y de j, pero no de n. Esta propiedad indica que el tiempo n no influye en la probabilidad de transici´on, por tanto se puede tener que P (Xn+1 = j/Xn = i) = P (X1 = j/X0 = i), en donde X0 indica el estado inicial del proceso. Un proceso estoc´astico {Xn ; n ∈ N} que cumple con la propiedad markoviana y de estacionariedad se denomina Cadena de Markov homog´enea.

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

3 / 32

Matriz de transici´on Se acostumbra a presentar las probabilidades de transici´ on como las componentes de una matriz P de n × n, en donde n corresponde al n´ umero de estados que puede tomar la cadena. Ejemplo: Consideremos nuevamente el lanzamiento de una moneda honesta que se lanza varias veces al aire. Sea Xk el resultado del lanzamiento de la moneda en el k-´esimo lanzamiento. Sabemos que ΩXk = {cara, sello}, adem´as #ΩXk = 2, por lo tanto la matriz de transici´ on (en una etapa) es:

cara

cara

sello

p11

p12

P = sello

p21

p22

!



=

1/2

1/2

1/2

1/2

 

Este tipo de matrices se P denominan matrices estoc´asticas debido a que, para cualquier fila i, se tiene j pij = 1. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

4 / 32

Diagrama de Transici´on Es posible representar gr´aficamente una cadena de Markov mediante una grafo dirigido, en el cual cada estado es representado por un nodo y cada probabilidad de transici´ on pij > 0 es representada por un arco entre los nodos i y j. En el ejemplo del lanzamiento de la moneda el diagrama de transici´on es el siguiente: 1 2 1 2

cara

sello

1 2

1 2

¿Este proceso corresponde a una cadena de Markov?

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

5 / 32

Probabilidad de Transici´on de n-etapas Probabilidad de Transici´on de n-etapas Se denota por pij (n) la probabilidad que la cadena pase del estado i al estado j despu´es de n etapas. Es decir, si {Xn ; n ∈ N} es una cadena de Markov entonces: pij (n) = P (Xm+n = j/Xm = i) Ejemplo: Consideremos la probabilidad de transici´ on de dos etapas pij (2) definida como pij (2) = P (Xm+2 = j/Xm = i). Si asumimos m = 0, entonces X pij (2) = P (X2 = j/X0 = i) = P (X2 = j, X1 = k/X0 = i) k

=

X

P (X2 = j/X1 = k, X0 = i)P (X1 = k/X0 = i)

k

=

X

P (X2 = j/X1 = k)P (X1 = k/X0 = i)

k

=

X

pik pkj

k

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

6 / 32

Ecuaciones de Chapman-Kolmogorov El siguiente resultado establece una clase de ecuaciones las cuales entregan una generalizaci´ on del resultado del ejemplo anterior.

Ecuaciones de Chapman-Kolmogorov Para todo 0 < r < n se tiene pij (n) =

X

pik (r)pkj (n − r).

k

Esta proposici´ on establece que la probabilidad de ir desde el estado i hasta el estado j al finalizar n transiciones es el producto entre la probabilidad de ir desde el estado i hasta un estado intermedio k despu´es de r transiciones y la probabilidad de ir desde el estado k al estado j despu´es de n − r transiciones. La demostraci´on de este resultado sigue el mismo esquema que el ejemplo anterior para el caso n = 2.

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

7 / 32

Matriz de transici´on de n-etapas Si denotamos por P (n) la matriz de las probabilidades de transici´on de n-etapas pij (n), entonces las ecuaciones de Chapman-Kolmogorov establecen que P (n) = P (r) · P (n−r) donde P (1) = P . Observaci´ on: Si un proceso consta s´ olo de dos estados, entonces   p11 (n) p12 (n)  P (n) =  p21 (n) p22 (n)

¿C´ omo calcularemos P (n) ?. Notemos que si n = 2 y r = 1, entonces P (2) = P (1) · P (2−1) = P · P (1) = P · P = P 2

Ahora observemos que si n = 3 y r = 1, entonces P (3) = P (1) · P (3−1) = P · P (2) = P · P 2 = P 3 Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

8 / 32

Matriz de transici´on de n-etapas Por lo tanto, P (n) = P n Ejemplo: Una part´ıcula salta entre dos posiciones A y B seg´un una cadena de Markov con las siguientes probabilidades:

0,4 0,6

A

B

0,8

0,2 Si la part´ıcula inicialmente se encuentra en la posici´ on A, determine la probabilidad de que est´e en A y en B despu´es de 1

1 etapa

2

2 etapas

3

n etapas Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

9 / 32

Matriz de transici´on de n-etapas

Recordemos que si una matriz cuadrada P es diagonalizable, entonces P = U · D · U −1 donde D es matriz diagonal que contiene los valores propios de P . U corresponde a la matriz cuyas columnas son los vectores propios de P . Para calcular la potencia de una matriz diagonalizable simplemente se utiliza P n = U · Dn · U −1

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

10 / 32

Distribuci´on del proceso en la n-´esima etapa Si deseamos conocer la distribuci´ on (incondicional) de la cadena para una etapa cualquiera utilizaremos un vector columna, que denotaremos por f (n) , con tantas posiciones como estados de la forma siguiente:     p1 (n) P (Xn = 1)          p2 (n)   P (Xn = 2)                  .. ..     . . (n)     f = =       pj (n)   P (Xn = j)          ..     .     ..     . pN (n) P (Xn = N )

donde N = #ΩXk

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

11 / 32

Distribuci´on del proceso en la n-´esima etapa Si utilizamos el teorema de probabilidad total sobre pj (n) = P (Xn = j) condicionando sobre el estado inicial del proceso, tendremos: pj (n) = P (Xn = j) X P (Xn = j/X0 = i)P (X0 = i) = i

=

X

pij (n)pi (0)

i

Luego, es claro que f (n) = [P (n) ]T · f (0) para cualquier n ∈ N. Observaci´ on: Recordar que 

p11 (n) p12 (n)

   p21 (n) p22 (n)   p31 (n) p32 (n) Fabi´ an Mancilla (Usach)

p13 (n)

T



p11 (n) p21 (n)

     p23 (n)  =   p12 (n) p22 (n)   p33 (n) p13 (n) p23 (n) Modelos Estoc´ asticos

p31 (n)



  p32 (n)    p33 (n) 12 / 32

Tiempos de Primera Pasada Ejemplo: En el problema anterior de la part´ıcula, ¿Cu´al es la distribuci´ on de probabilidad de la tercera etapa?

Tiempos de Primera Pasada Supongamos ahora que, para una cadena de Markov cualquiera, nos interesa saber el tiempo que demora el proceso en pasar del estado inicial i a un estado j. Este tiempo es una variable aleatoria que la denotaremos en general por T (i, j) y la llamaremos tiempo de primera pasada. Para conocer la distribuci´ on de probabilidades de T (i, j) definamos, Fk (i, j) = P (T (i, j) = k) = P (X1 6= j, X2 6= j, . . . , Xk−1 6= j, Xk = j/X0 = i) Para k = 1 se tiene que, F1 (i, j) = P (X1 = j/X0 = i) = pij Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

13 / 32

Tiempos de Primera Pasada Para k = 2 tenemos, F2 (i, j) = P (X1 6= j, X2 = j/X0 = i) =

X

P (X1 6= j, X2 = j/X0 = i, X1 = m)P (X1 = m/X0 = i)

X

P (X1 6= j, X2 = j/X1 = m)pim

X

F1 (m, j)pim =⇒ F2 (i, j) =

m6=j

=

m6=j

=

m6=j

Fabi´ an Mancilla (Usach)

X

pim F1 (m, j)

m6=j

Modelos Estoc´ asticos

14 / 32

Tiempos de Primera Pasada Para k = 3 tenemos, F3 (i, j) = P (X1 6= j, X2 6= j, X3 = j/X0 = i) =

X

P (X1 6= j, X2 6= j, X3 = j/X0 = i, X1 = m)P (X1 = m/X0 = i)

X

P (X1 6= j, X2 6= j, X3 = j/X1 = m)pim

X

F2 (m, j)pim =⇒ F3 (i, j) =

m6=j

=

m6=j

=

m6=j

En general, Fk (i, j) =

X

pim F2 (m, j)

m6=j

X

pim Fk−1 (m, j).

m6=j

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

15 / 32

Tiempos de Retorno De esta forma se obtiene el siguiente sistema recursivo:  F1 (i, j)   

= pij

   Fk (i, j) =

X

pim Fk−1 (m, j)

m6=j

Ejemplo: En el problema anterior de la part´ıcula, ¿Cu´al es la distribuci´ on del tiempo de primera pasada al estado B (es decir la distribuci´ on de T (A, B))?

Tiempos de Retorno Se denomina tiempo de retorno al estado i a la variable aleatoria T (i, i) = Ti . Por lo tanto, la probabilidad de retorno en k etapas al estado i es Fk (i, i). Ejemplo: En el problema anterior de la part´ıcula, ¿Cu´al es la distribuci´ on del tiempo de retorno al estado A (es decir la distribuci´ on de T (A, A))? Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

16 / 32

Tiempos de Retorno Tiempos de Retornar Alguna Vez Denotaremos como F (i, i) a la probabilidad de retornar alguna vez al estado i. Esta probabilidad corresponde a sumar las probabilidades de retornar en una etapa, dos etapas, tres etapas, etc´etera. Es decir, P (Ti < ∞) = F (i, i) =

∞ X

Fk (i, i)

k=1

Ejemplos: 1

En el problema anterior de la part´ıcula, ¿Cu´al son las probabilidades de retornar alguna vez al estado A y al estado B?

2

Dada la siguiente matriz de transici´ on correspondiente a una cadena de Markov dibuje el grafo asociado y calcule F3 (1, 2) y F4 (3, 1).   0,4 0,2 0,3 0,1  0,1 0,9 0 0   P =  0 0,5 0,5 0  0,1 0 0,4 0,5 Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

17 / 32

Clasificaci´on de estados Clasificaci´on de estados Dada una cadena de Markov es posible clasificar sus estados de acuerdo a las siguientes definiciones: Un estado i se dice que es transiente si, comenzando en ese estado, existe una probabilidad no nula de que nunca regresemos a i. En este caso, si el estado i es transiente, entonces F (i, i) < 1. Un estado i se dice que es recurrente si, comenzando en ese estado, con probabilidad 1 el proceso retornar´a alguna vez a i. Es este caso, si el estado i es recurrente, entonces F (i, i) = 1. Si E(T (i, i)) < ∞ se denominar´a recurrente positivo. Si E(T (i, i)) = ∞ se denominar´a recurrente nulo (caso #Ω = ∞). Un estado i se dice que es absorbente si es imposible abandonarlo una vez que la cadena entra a ´este. En este caso, si el estado i es absorbente, entonces pii = 1 y pij = 0 para todo i 6= j. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

18 / 32

Clasificaci´on de estados Ejemplo: Considere el siguiente diagrama de transici´ on asociado a una cadena de Markov. 1 2

2 3

1 1 2

2 1 4 1 2 3 4

3 1 2

4 1 2

Determine si hay estados transientes, recurrentes o absorbentes. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

19 / 32

Clasificaci´on de estados Comunicaci´on entre estados Se dice que los estados i y j se comunica si existe un camino de i a j con un n´umero finito de etapas, y viceversa (de j a i). En el ejemplo anterior, los estados 2, 3 y 4 se comunican entre s´ı, pero no as´ı los estados 1 y 2. Esta propiedad de comunicaci´ on establece una relaci´ on entre los estados que permite definir clases de estados, compuestas por todos los estados que se comunican entre s´ı. Estas clases de estados son disjuntas entre s´ı y cubren todo el conjunto de estados. En el ejemplo anterior el estado 1 constituye una clase y los estados 2, 3 y 4 otra, es decir C1 = {1}, C2 = {2, 3, 4}. Si una cadena de Markov tiene una sola clase de estados, se dir´a que es irreducible. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

20 / 32

Periodicidad Estados peri´odicos Un estado es peri´odico si, partiendo de ese estado, s´ olo es posible volver a ´el en un n´umero de etapas que sea m´ ultiplo de un cierto n´ umero entero mayor a uno. En otras palabras, el estado j es peri´ odico si existe n ≥ 1 tal que Fk (j, j) > 0 s´ olo para valores de k en el conjunto {n, 2n, 3n, 4n . . .}. un divisor de los k para los El per´ıodo d del estado j corresponde al m´aximo com´ cuales Fk (j, j) > 0. Si d > 0 diremos que el estado es peri´ odico con per´ıodo d Si d = 1 diremos que el estado es aperi´ odico. odicos. Los estados recurrentes positivos aperi´ odicos se denominan estados erg´ Una cadena de Markov que continen s´ olo estados erg´ odicos se denomina cadena erg´ odica.

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

21 / 32

Periodicidad Ejemplo: En la siguiente cadena de Markov, los retornos al estado 2 se pueden producir en las etapas 2, 3, 4, 5, 6, 7, 8, . . . Luego d = 1 y el estado 2 es aperi´odico. ¿Qu´e sucede con los per´ıodos de los estados 3 y 4?

1 2 4 3

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

22 / 32

Periodicidad Ejemplo: ¿Cu´antas clases existen en la siguiente cadena de Markov? ¿Cu´al es el per´ıodo del estado 1? ¿Cu´al es el per´ıodo de los otros estados?

1 2

4 3

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

23 / 32

Periodicidad Observaci´ on: Es posible demostrar que todos los estados de una clase son del mismo tipo: transientes, recurrentes nulos o recurrentes positivos, y aperi´odicos o peri´odicos con el mismo per´ıodo. Ejemplo: Consideremos la siguiente matriz de probabilidades de transici´on:   1 0 0      1/2 1/6 1/3 P =     1/3 3/5 1/15 1

Dibuje el diagrama de transiciones.

2

Obtenga la distribuci´ on de T1 .

3

Calcule la probabilidad de retornar alguna vez al estado 1, es decir F (1, 1).

4

Calcule P (T (1, 1) = ∞).

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

24 / 32

Estado del proceso en el Largo Plazo Sabemos que la distribuci´ on de probabilidades del proceso en la etapa n est´a dada por, f (n) = [P n ]T · f (0) Diremos que el proceso tiene distribuci´ on l´ımite si existe el l´ımite l´ım f (n) . n→∞

En la medida que esto ocurra, podemos concluir que, pasado mucho tiempo, la distribuci´ on de probabilidades del proceso no cambia de una etapa a otra. El valor del l´ımite puede o no depender del vector de probabilidades inicial f (0) . En el caso que el l´ımite exista y su valor no dependa de f (0) , diremos que el on estacionaria. Bajo esta situaci´ on, las condiciones proceso tiene distribuci´ iniciales del sistema tienden a ser irrelevantes para efectos de su comportamiento en el largo plazo.

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

25 / 32

Estado del proceso en el Largo Plazo Para obtener algunas probabilidades l´ımites, existen los siguientes resultados:

Probabilidades L´ımites de una Cadena de Markov 1

Si j es un estado transiente o recurrente nulo entonces l´ım pjj (n) = 0

n→∞ 2

Si j es un estado recurrente positivo aperi´ odico entonces l´ım pjj (n) =

n→∞

3

1 >0 E(Tj )

Si j es un estado recurrente positivo peri´ odico, de per´ıodo d, entonces l´ım pjj (nd) =

n→∞

Fabi´ an Mancilla (Usach)

1 >0 E(Tj )

Modelos Estoc´ asticos

26 / 32

Estado del proceso en el Largo Plazo Probabilidades L´ımites de una Cadena de Markov 1

Si j es un estado recurrente positivo aperi´ odico entonces l´ım pij (n) =

n→∞ 2

F (i, j) ≥0 E(T (i, j))

Si j es un estado transiente o recurrente nulo entonces l´ım pij (n) = 0

n→∞ 3

Si i y j son estado recurrentes positivos pertenecientes a una misma clase, de per´ıodo d, entonces l´ım pij (n(i, j) + nd) =

n→∞ 4

1 ≥0 E(T (i, j))

Si i es transiente y j es recurrente, y asumiendo que F (i, j) > 0, los caminos que conducen de un estado a otro no son necesariamente del mismo largo. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

27 / 32

Estado del proceso en el Largo Plazo Las siguientes proposiciones establecen las condiciones para la existencia de una distribuci´ on estacionaria. En este caso denotaremos por π al vector de distribuci´ on estacionaria, es decir, πj = l´ım pj (n) = l´ım pij (n), independiente de i n→∞

n→∞

Distribuci´on Estacionaria 1

Existe una distribuci´ on estacionaria π tal que πj > 0 para todo j si y s´ olo si la cadena de Markov es irreducible, con estados recurrentes positivos aperi´ odicos.

2

Consideremos una cadena de Markov con espacio de estados S tal que S = C ∪ T , en que C es una clase de estados recurrentes positivos y T es un conjunto de una o m´as clases de estados transientes. Entonces existe una distribuci´ on estacionaria π. Adem´as, πj > 0 para todo j ∈ C y πj para todo j ∈ T. Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

28 / 32

Estado del proceso en el Largo Plazo En general, si se puede garantizar la existencia de una distribuci´ on estacionaria, su obtenci´ on puede lograrse por la v´ıa de resolver un sistemas de ecuaciones lineales, tal como se plantea en el siguiente resultado.

Obtenci´on de la Distribuci´on Estacionaria Si una cadena de Markov tiene una distribuci´ on estacionaria π en que πj > 0 para alg´un j, entonces π corresponde a la ´ unica soluci´on del sistema: πT = πT P X πi = 1 πi ≥ 0

Ejemplo: Determinar si existe distribuci´ on estacionaria en la siguiente cadena de Markov,   1/2 1/2 0 P =  0 1/3 2/3  1/3 1/3 1/3 Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

29 / 32

Estado del proceso en el Largo Plazo

Tarea: En un Estado socialista hay un economista que est´a muy interesado en estudiar el siguiente mecanismo de redistribuci´ on del capital entre los habitantes. Cada habitante es visitado diariamente por un inspector del Ministerio. Si ´el descubre que su capital neto es cero, entonces con probabilidad pi > 0 le entrega i unidades monetarias (i = 1, 2, 3, . . .). Por el contrario, si el inspector lo encuentra con un capital positivo j, se lo quita (para darlo, presumiblemente con probabilidad pj a otro habitante que tiene capital cero). Con este proceso, el economista asegura que, cualquiera sea la distribuci´ on inicial de capital, en el largo plazo, se obtendr´a una distribuci´ on equitativa del capital diario para cada habitante. ¿Ud. que opina? (modelar como una cadena de Markov y justificar).

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

30 / 32

Estado del proceso en el Largo Plazo Una matriz de transici´on P se dice que es doblemente estoc´astica si la suma de cada una de su filas y columnas es 1. Este tipo de matrices poseen la siguiente propiedad:

Matriz Doblemente Estoc´astica Si P es una matriz doblemente estoc´astica asociada a una cadena de Markov con N estados, y asumiendo que existe distribuci´ on estacionaria π, entonces πi =

1 , para todo i = 1, 2, . . . , N. N

Ejemplo: Determinar la distribuci´ on estacionaria en la siguiente cadena de Markov,   0,4 0,5 0,1 P =  0,3 0,3 0,4  0,3 0,2 0,5

Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

31 / 32

Aplicaciones de las Cadenas de Markov Una empresa tiene en un inventario un cierto producto para satisfacer la demanda de sus clientes. Sea Xn el n´umero de ´ıtemes en inventario al principio del d´ıa n. Sea Y1 , Y2 , . . . , Yi , . . . las demandas sucesivas en los d´ıas 1, 2, . . . , etc. Asumamos que ´estas corresponden a v.a. iid, en donde P (Yi = k) = ak . La pol´ıtica de inventario est´a determinada por dos par´ametros, s y S, y opera de la siguiente manera: al final de cada d´ıa se revisa el nivel de inventario y si ´este es menor que s, se pone una orden de stock para elevar el nivel de inventario hasta el valor S. Los nuevos ´ıtemes del producto est´an disponibles al principio del d´ıa siguiente. La demanda que no puede ser satisfecha se pierde. Luego, se puede deducir que   Xn − Yn , si Xn − Yn ≥ s Xn+1 =  S, si Xn − Yn < s ¿Es el proceso {Xn , n ∈ N} una cadena de Markov? Fabi´ an Mancilla (Usach)

Modelos Estoc´ asticos

32 / 32