• Author / Uploaded
• Maria Javiera Sepúlveda Alamos

Citation preview

Escuela de Ingeniería Industrial Universidad del Valle

Cadenas de Markov

AGRADECIMIENTOS AL PROFESOR JUAN JOSE BRAVO, MsC

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.

CADENAS DE MARKOV Proceso estocástico de tiempo discreto con espacio de estados finito No se conoce el estado futuro de la variable pero se dispone de cierta información probabilística respecto a su evolución Estados e instantes de tiempo

{Xt}  Característica de interés que evoluciona en el tiempo de manera probabilística Si Xt=i, se dice que el proceso estocástico está en el estado i en el tiempo t Sea Pij la probabilidad de estar en el estado j en el momento t+1, dado que en el momento t se encuentra en el estado i

INSTANTES DE TIEMPO

Momentos en los que es probable que se den cambios de estado de la variable aleatoria Momentos en los que nos interesa inspeccionar el estado de la variable aleatoria

Sincrónicos o asincrónicos La distribución de probabilidad asociada difiere para cada intervalo de tiempo definido para la variable

CÓMO DEFINIR INSTANTES Y ESTADOS? Conocimiento del sistema Experiencia Estudios

Grado de conocimiento del sistema Estadísticas

Condiciones particulares e intrínsecas del sistema Funcionalidad y requerimiento de los resultados Características particulares de estudio

LA MEMORIA TEMPORAL DE LA CADENA DE MARKOV Pensemos en la secuencia de Estados para la Variable Aleatoria Xt cambiante con respecto al tiempo.

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

Estado Actual

Xt-1=m,

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

Estados Pasados

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.

LA MEMORIA TEMPORAL DE LA CADENA DE MARKOV

La probabilidad condicional P(Xt+1=j / Xt=i) existe Propiedad Procesos Markovianos

Pij

Xt

1

j / X0 Pij

k0 , X1 k1 , ..., Xt Xt

1

j / Xt

i

1

kt 1 , Xt

i

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 y entender el comportamiento del sistema a través del tiempo.

Procesos de planeación de largo plazo

PROBABILIDADES DE TRANSICIÓN

A la probabilidad condicional P(Xt+1=j/Xt=i) se le llama Probabilidad de Transición del estado i al estado j y se simboliza con pij.

Xt+1=j , Xt=i Estado Futuro

Estado Actual

Observe que al evaluar pij 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.

pij

(1) ij

p

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

CADENAS DE MARKOV HOMOGÉNEAS Si la probabilidad P(Xt+1=j / Xt=i) ó pij es igual para cualquier t Es decir…….. P(X1=j / X0=i) =……= P(X5=j / X4=i) =………= P(Xt+1=j / Xt=i)

P Xt

1

j / Xt

i

P X1

j / X0

i

t

En este caso se dice que la probabilidad de transición del estado i al j es estacionaria.

Supuesto

Las probabilidades de transición no cambian con el tiempo

ACIONES DEL SUPUESTO DE LAS PROBABILIDADES ESTACION

(1)

(n)

Si pij , es decir pij es estacionaria, entonces, pij también es estacionaria ó no cambia con el tiempo.

pij

(n)

Probabilidad P(Xt+n=j / Xt=i) y se le conoce como probabilidad de transición de n pasos.

En el curso se tomará como válido el supuesto de las probabilidades de transición estacionarias.

MATRIZ DE PROBABILIDADES DE TRANSICIÓN DE “UN PASO” Matriz de Probabilidades de Transición de un paso de una Cadena de Markov de 5 estados.

Pij

P00 P10 P20 P30 P40

P01 P11 P21 P31 P41

P02 P12 P22 P32 P42

P03 P13 P23 P33 P43

P04 P14 P24 P34 P44

Recordando un poco la definición de espacio muestral.....veamos la FILA 2 de la matriz anterior: P(Xt

0 / Xt 1) P(Xt 1 / Xt 1) P(Xt

2 / Xt 1) P(Xt

3 / Xt 1) P(Xt

Cada fila de Pij corresponde a un espacio muestral

P10 + P11 + P12 + P13 + P14 = 1

4 / Xt 1)

1

EN RESUMEN …

Las probabilidades de transición definen la matriz P = [pij] que satisface 1)

pij

(n)

0

i, j, n

M 2)

pij j o

( n)

1

i, n

MATRICIALMENTE…

n 00

n ij

P

n 0M

p ... p : : : n n pM 0 ... pMM

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

Después de muchos estudios sobre el clima, se ha 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. Además, 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” (2) Estados:

Soleado y Nublado

Periodo de transición entre estados:

P(X1 = nublado/ X0 = nublado)=

0.4

P(X1 = nublado/ X0 = soleado)=

0.3

P(X1 = soleado/ X0 = nublado)=

0.6

P(X1 = soleado/ X0 = soleado)=

0.7

Pt t 1

=

Un día

Estados

Soleado

Nublado

Soleado

0,7

0,3

Nublado

0,6

0,4

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

(0) P( X 0 soleado) 0 P( X 0 nublado) 1 nublado(0) soleado

(0)

(0),

soleado

(0)

nublado

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” (4)

P(X1 nublado) P( X1 nublado/ X 0 nublado)xP( X 0 nublado) P( X1 nublado/ X 0 soleado)xP( X 0 soleado) Por lo tanto:

P(X1 nublado) ( 0.4 )x(1) ( 0.3 )x( 0 ) 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),

soleado

(1)

nublado

0.6, 0.4

EJEMPLO DE MATRIZ DE TRANSICIÓN DE “UN PASO” (5) CONCLUSIÓN

0.7 0.3 soleado( 0 ), nublado( 0 ) * 0.6 0.4 Estado Inicial del Sistema

Matriz de Transición

( 1 ),

soleado

Probabilidad del Estado final del sistema

En general, se tiene que para cualquier cadena de Markov`

(1)

( t 1) (n)

(1)

nublado

( 0 )xP10

( t )Ptt 1

( 0)xP10P12 .. Pnn 1

( 0 )Pn

Departamento de Ciencias de la Ingeniería y Producción Pontificia Universidad Javeriana

Ejercicios de construcción de matrices de transición

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).

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.

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).

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

INTERPRETACIÓN MATRIZ DE PROBABILIDADES DE TRANSICIÓN Considere el ejemplo del valor de una acción. Al final de un día dado se registra el precio. Si la acción subió, la probabilidad de que suba mañana es 0.7. Si la acción bajó, la probabilidad de que suba mañana es sólo 0.5. Esta es una cadena de markov con los siguientes estados: Estado 0: el precio de la acción sube Estado 1: el precio de la acción baja

P

La matriz de transición está dada por

0.7 0.3 0.5 0.5

Ahora interprete esta matriz de transición Estado 0: la acción aumentó hoy y ayer. Estado 1: la acción aumentó hoy y ayer bajó. Estado 2: la acción bajó hoy y ayer aumentó Estado 3: la acción bajó hoy y ayer

P

0.9 0 0.1 0 0.6 0 0.4 0 0 0.5 0 0.5 0 0.3 0 0.7

Ejemplo: Considere el estado del tiempo donde el llover mañana depende si llovió o no ayer y hoy

Estado 0

Llovió ayer y hoy

Estado 1

No Llovió ayer y llovió hoy

Estado 2

Llovió ayer y No llovió hoy

Estado 3

No llovió ni ayer ni hoy

La matriz de transición de un paso es la siguiente: 0 - LL

P= Ayer y Hoy

0,7 0,5

0 0

0,3 0,5

0 0

0 0

0,4 0,2

0 0

0,6 0,8

0 - LL

1 - NL

2 - LN

3 - NN

1- NL

2 - LN 3 - NN

Hoy y Mañana 0,5

0,5

1

0,4 0,7

0

0,2

2

0,3 0,6 3

0,8

Suponga que le preguntan, cuál es la probabilidad de que llueva pasado mañana dado que llovió ayer y hoy? 0,7 0,5 0 0

2

P=

2

P=

0 0 0,4 0,2

0,3 0,5 0 0

0 0 0,6 0,8

0,49 0,35 0,20 0,10

0,12 0,20 0,12 0,16

LL

NL

X

0,7 0,5 0 0

0,21 0,15 0,20 0,10 LN

Hoy y Mañana

0 0 0,4 0,2

0,3 0,5 0 0

0,18 0,30 0,48 0,64 NN

0 0 0,6 0,8 LL NL Ayer y LN Hoy NN

P(llueva pasado mañana/ llovió ayer y hoy)= P(llueva mañana y pasado mañana / llovió ayer y hoy) + P(no llueva mañana y llueva pasado mañana / llovió ayer y hoy)

0.49 + 0.12 = 0.61

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2,…...las demandas de esta cámara durante la primera, segunda,…. 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 que se tienen al final de la semana dos, etc. Suponga que X0 = 3 El sábado en la noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. 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 cero s = 0 (no hay cámaras en la tienda), ordenar hasta 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).

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (2) Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {Xt} para t = 0, 1, … es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana. Las Variables aleatorias Xt, son dependientes y se pueden evaluar en forma iterativa por medio de la expresión:

Xt

1

Max (3 - Dt 1 ), 0 si X t 1 Max ( X t - Dt 1 ), 0 si X t 1

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (3) Suponiendo que cada Dt, tiene una distribución Poisson con Donde Dt son las demandas de cámaras en la semana t

= 1,

Para obtener P00 es necesario evaluar: P{Xt = 0 / Xt-1 = 0}

Xt

1

Max (3 - Dt 1 ), 0 si X t 1 Max ( X t - Dt 1 ), 0 si X t 1

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (4) Si Xt-1=0

P00

Xt={Max(3-Dt+1), 0}

P Dt 3 1 P Dt 0 1 - P Dt 2 P Dt 1

P Dt

0 k

Dado que la demandase consideraPoisson Demanda

Probabilidad

2

(1)2e(-1)/2!= 0,18394

1

(1)1e(-1)/1!= 0,18394

0

(1)0e-(1)/0!= 0.367879

e k!

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (5)

P10 =:P{Xt = 0 / Xt-1 = 1} Si Xt-1=1

P10

Xt={Max(1- Dt), 0}

P Dt 1 1 P Dt 1 - 0,367879 0,632

0

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (5)

P21 =:P{Xt = 1 / Xt-1 = 2} Si Xt-1=2

P21 P D 1

Xt={Max(2-Dt), 0}

0.368

EJEMPLO DE USOS DE LAS CADENAS DE MARKOV (7)

De forma similar se obtienen las demás probabilidades

ECUACIONES DE CHAPMAN - KOLMOGOROV

pij

(n)

M

pik ( m ) pkj( n

m)

i 0,1,...,M j 0,1,...,M

k o

m 1,2,...,n -1 n m 1, m 2,... Ir del estado i al estado j en n pasos, implica que el proceso podría estar en el estado k después de exactamente m pasos (m < n).

Pik(m): Probabilidad de ir del estado i al estado k en m pasos Pkj (n-m): Probabilidad de ir del estado k al estado j en (n-m) pasos M

M

Si m 1

pij

( n)

pik pkj

(n 1)

Si m n -1

pij

(n)

pik (n k o

k o M

Si n 2

pij (2)

pik pkj

P (2) P * P P 2

k o

P

(n)

(n-1)

PP

P

(n-1)

P P

n

1)

pkj

MATRIZ DE PROBABILIDADES DE TRANSICIÓN DE “N PASOS”

Pij

( 2)

Pij Pij

P00 P10 P20 P30 P40

P01 P11 P21 P31 P41

P02 P12 P22 P32 P42

P03 P13 P23 P33 P43

P04 P14 P24 P34 P44

P00 P10 P20 P30 P40

X

P01 P11 P21 P31 P41

P02 P12 P22 P32 P42

P03 P13 P23 P33 P43

P04 P14 P24 P34 P44

Y generalizando a “n pasos” ( n)

P00 P10 Pij Pij Pij ...... P P20 P30 n - veces Según la Ecuación de P40 ( n)

Pij (n)

( n)

ij

( n)

( n)

Chapman-Kolmogorov

( n)

( n)

( n)

( n)

P01 P11 P21 P31 P41

P02 P12 P22 P32 P42

P03 P13 P23 P33 P43

P04 P14 P24 P34 P44

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

( n)

Esta probabilidad suele ser útil cuando el sistema se encuentra en estado i y se desea la probabilidad de que el sistema se encuentre en el estado j después de n períodos de tiempo.

ECUACIONES DE CHAPMAN - KOLMOGOROV

ECUACIONES DE CHAPMAN - KOLMOGOROV

Cuando n no es muy grande la matriz de transición de n pasos se puede calcular fácilmente, pero si n es muy grande los cálculos resultan tediosos y los errores de redondeo pueden causar inexactitudes

La Matriz de Transición de 2 Pasos para el Caso del Almacén de Cámaras

P2

0.249 0.283 0.351 0.249

0.286 0.252 0.319 0.286

0.300 0.233 0.233 0.300

Cuál es la probabilidad

0.165 que teniendo ahora una 0.233 cámara haya exactamente cero 0.097 cámaras en inventario en 0.165 dos semanas?

Cuál es la probabilidad que teniendo ahora una cámara haya exactamente tres cámaras en inventario en dos semanas?

La Matriz de transición de 4 pasos

P4=

0.249 0.283 0.351 0.249

0.286 0.252 0.319 0.286

P4=

0.289 0.281 0.284 0.289

0.286 0.285 0.283 0.286

0.300 0.233 0.233 0.300

0.261 0.267 0.263 0.261

0.165 0.233 0.097 * 0.165

0.164 0.166 0.171 0.164

0.249 0.283 0.351 0.249

0.286 0.252 0.319 0.286

0.300 0.233 0.233 0.300

0.165 0.233 0.097 0.165

Por favor construir P8

Qué tiene de particular? Se dice que estas son las probabilidades del estado estable

PROBABILIDADES INCONDICIONALES Probabilidades del estado estable

n

(n) (0)

(0)P 0 (0)

1(0) ....

M (0)

pij( n )

P00(n) . . . (n) PM0

(n) ... P0M ... . ... . ... . (n) ... PMM

Si se desea la probabilidad incondicional P{Xn=j} es necesario que se especifique la distribución de probabilidad del estado inicial, o sea P{X0=i} para i desde 1 hasta M, entonces:

P{ X n

j } P{ X 0

0 }P0nj P{ X 0 1}P1nj ... P{ X 0

M }PMjn

Si en el ejemplo anterior, se supuso que el inventario inicial era tres cámaras, la probabilidad incondicional de que haya tres cámaras en inventario después de dos semanas es P{X2=3} = (1)p33(2)=0,165

LA EVOLUCIÓN DE UN PROCESO ESTOCASTICO ¿Cómo simular la evolución de un proceso estocástico caracterizado por la siguiente matriz de probabilidades de transición? P=

0.080 0.632 0.264 0.080

0.184 0.368 0.368 0.184

0.368 0.000 0.368 0.368

0.368 0.000 0.000 0.368

Recordando que cada fila corresponde a un Espacio Muestral definido.

Se debe analizar (ó simular) fila por fila de la matriz, según la información requerida acerca del proceso

1 0.632 0.264 0.080

fda (función de distribución acumulada) para la Fila 1 y Fila 4 Resultados posibles

LA EVOLUCIÓN DE UN PROCESO ESTOCASTICO Comportamiento simulado de los inventarios en cada una de las siguientes 100 semanas

Xo =3

Para simular la Semana 1,ó X1, se inicia simulando la Fila 4, dado que se observará la transición desde el estado 3. Pasos a seguir:

1 0.632 0.264 0.080

a) Genere un aleatorio entre 0 y 1 en Excel fda Fila 4

Simular lo que sucedería en las demás semanas

b) Tomo la decisión con este criterio: • Si ALEATORIO() ≤ 0.08

X1=0

• Si 0.08 < ALEATORIO() ≤ 0.264

X1=1

• Si 0.264 < ALEATORIO() ≤ 0.632 • Si 0.632 < ALEATORIO() ≤ 1

X1=2 X1=3

LA MATRIZ P(n) Y LOS ÁRBOLES DE DECISIÓN

A MATRIZ DE TRANSICIÓN DE UN PASO

0.2 0.5 0.3

P=

A B C

0.2 0.5 0.3

B

C

0.2 0.5 0.7 0.2 0.3 0.6

0.3 0.1 0.1

0.48 0.38 0.14 P(2)= P. P = 0.7 0.2 0.1 x 0.7 0.2 0.1 = 0.31 0.45 0.24 0.51 0.33 0.16 0.3 0.6 0.1 0.3 0.6 0.1

LA MATRIZ P(n) Y LOS ÁRBOLES DE DECISIÓN

0.2

A

0.2

A

0.5

B

0.3

C

0.7

A

0.2

B

0.1

C

0.3

A

0.6

B

0.1

C

0.5

B

A t=0

0.3

C t=1

Transición de t = 0 a t = 1

t=2

Transición de t = 1 a t = 2

LA MATRIZ P(n) Y LOS ÁRBOLES DE DECISIÓN Si se simbolizan los elementos de la matriz P(2) como:

A A

P(2) =

B C

p p p

( 2) AA ( 2)

BA ( 2)

CA

B ( 2)

p

AB

p p

( 2) BB ( 2)

CB

C ( 2)

p

AC

p p

( 2) BC ( 2)

CC

PAA(2)= (0.2) (0.2) + (0.5) (0.7) + (0.3) (0.3) = 0.48

PAB(2)= (0.2) (0.5) + (0.5) (0.2) + (0.3) (0.6) = 0.38 PAC(2)= (0.2) (0.3) + (0.5) (0.1) + (0.3) (0.1) = 0.14

TIEMPOS DE PRIMERA PASADA Con frecuencia es conveniente poder hacer afirmaciones en términos de probabilidades sobre el número de transiciones que hace el proceso al ir de un estado i a un estado j por primera vez.

Este lapso se llama tiempo de primera pasada al ir del estado i al estado j

TIEMPOS DE PRIMERA PASADA

Cuando j=1, este tiempo de primera pasada es justo el número de transiciones hasta que el proceso regresa al estado inicial i Ejemplo En el ejemplo del almacén de cámaras xi representa el número de cámaras al iniciar la semana t {xt} para t=1, 2, … , n es un proceso estocástico

El número posible de cámaras en inventario al final de la semana t son: Estados posibles del sistema [ 0 1 2 3 ] Suponga que ocurrió lo siguiente:

X0=3, X1=2, X2=1, X3=0, X4=3, X5=1, En este caso, • el tiempo de primera pasada para ir del estado 3 al estado 1 es dos semanas • Y el tiempo de recurrencia del estado 3 es cuatro semanas • El tiempo de primera pasada para ir del estado 3 al estado 0 es de tres semanas

TIEMPOS DE PRIMERA PASADA

0.48 0.38 0.14 0.31 0.45 0.24 (2) P = 0.51 0.33 0.16 Detalle el segundo elemento de la primera columna de la matriz P(2), 0.31, y el árbol de decisión del cual resulta. Note que, según el árbol

p

(2)

BA

( 0.7 )( 0.2 ) ( 0.2 )( 0.7 ) ( 0.1 )( 0.3 ) 0.31

Ahora, si se desea encontrar la probabilidad de pasar por primera vez del estado B al estado A, después de 2 períodos de tiempo, ésta probabilidad viene dada por:

f

(2) BA

( 0.2 )( 0.7 ) ( 0.1 )( 0.3 ) 0.17

f

(2) BA

(2) pBA

1 1) f BA p(AA 0,31 0,14 0,17

PROBABILIDADES DE PRIMERA PASADA 0.2 0.7

A B C

0.5

A

0.3 0.7

B

0.2

B

A B C

0.2 0.1 0.3

t=0 0.1

t=1

p

(n)

ij

f

(n) ij

p p

f

ij

*

p

( n 1) ji

f f

(2)

ij

t=2

(1)

(1)

ij

A B C

0.6 0.1

C

fij(n) denota la probabilidad de que el tiempo de primera pasada del estado i al estado j sea n

f

(2) ij

*

p

(1) ij (2) ij

(n 2) ji

p f

ij

...

(1) ij

f

*

p

( n 1) ij

jj

*

p

ji

PROBABILIDADES DE PRIMERA PASADA

f f

f

(n) ij

p

(n)

ij

f

(1) ij

(1)

(1)

p p

ij (2) ij

*

p f

ij

ij

(2)

ij

p

( n 1) ji

f

(1) ij

(2) ji

*

*

p

p

ji

(n 2) ji

...

f

( n 1) ij

*

p

ji

PROBABILIDADES DE PRIMERA PASADA

Para i y j fijos las fij son números no negativos tales que

n 1 Si

n 1

Si

n 1

(n) f ij

(n) f ij

(n) f ij

1

1

Un proceso que al iniciar en i puede no llegar nunca al estado j

1

Las fij(n) para n=1, 2, … pueden considerarse como una distribución de probabilidad para la variable aleatoria, el tiempo de primera pasada

TIEMPOS DE PRIMERA PASADA

Mientras que puede ser difícil calcular fij(n) para toda n, es relativamente sencillo obtener el tiempo esperado de primera pasada del estado i al estado j

si

(n)

1

(n)

1

nfij n 1

ij

nfij n 1

(n)

si

nfij n 1

TIEMPOS DE PRIMERA PASADA

Valor esperado del tiempo de primera pasada del estado i al estado j

nfij (n) 1

si n 1

ij

1

pik k j

kj

TIEMPOS DE PRIMERA PASADA

Ejemplo P=

0.080 0.632 0.264 0.080

0.184 0.368 0.368 0.184

0.368 0.000 0.368 0.368

ij

Para calcular el tiempo esperado hasta que ya no se tengan cámaras en el almacén podemos usar las anteriores ecuaciones

0.368 0.000 0.000 0.368

1

pik

kj

k j

30 20

10

1 p31 1 p21 1 p11

10 10

10

p32 p22 p12

20 20

20

p33 30 p23 30 p13 30

TIEMPOS DE PRIMERA PASADA

La solución simultanea a este sistema es:

El tiempo esperado para que el almacén se quede sin cámaras es 1.58, 2.51 y 3.50 semanas, dado que el proceso inicia con 1, 2 o 3 cámara respectivamente

DIAGRAMA DE TRANSICIÓN DE ESTADOS

El diagrama de transición de estados (DTE) de una Cadena de Markov es un grafo dirigido cuyos nodos son los estados de la Cadena y cuyos arcos se etiquetan con la probabilidad de transición entre los estados que unen. Si dicha probabilidad es nula, no se pone arco.

i

qij

j

EJEMPLO: LÍNEA TELEFÓNICA Sea una línea telefónica de estados ocupado=1 y desocupado=0. Si en el instante t está ocupada, en el instante t+1 estará ocupada con probabilidad 0,7 y desocupada con probabilidad 0,3. Si en el instante t está desocupada, en el t+1 estará ocupada con probabilidad 0,1 y desocupada con probabilidad 0,9.

Q

0,9 0,1 0,3 0,7

0,1 0,9

0

1 0,3

0,7

GRAFOS

Clasificación de Estados

CLASIFICACIÓN DE ESTADOS DE UNA CADENA DE MARKOV EJEMPLO: Suponga que un jugador tiene $1 y que cada jugada paga $1 con probabilidad p>0 ó pierde $1 con probabilidad 1-p. El juego termina cuando el jugador acumula $3 ó bien cuando quiebra. Este juego es una cadena de Markov en la que los estados posibles son la fortuna del jugador, es decir, $0, $1, $2 y $3.

P=

Estados accesibles

0 1 2 3

0 1 1-p 0 0

1 0 0 1-p 0

2 0 p 0 0

3 0 0 p 1

Un estado j es accesible desde un estado i si Pij(n)>0 para alguna n. Ej: el estado 2 no es accesible desde el 3, mientras que el estado 3 si es accesible desde el 2.

Estados que se comunican

Si el estado i es accesible desde el estado j, y el estado j es accesible desde el estado i, entonces se dice que los estados j e i se comunican. Ej: en el ejemplo del jugador observe que el estado 2 es accesible desde el estado 1, y el estado 1 es accesible desde el estado 2, por lo tanto los estados 1 y 2 se comunican.

2. Si el estado i se comunica con el estado j, el estado j se comunica con el estado 1

3. Si el estado i se comunica con el estado j y el estado j se comunica con el estado k, entonces el estado i se comunica con el estado k

Definición de Clase

Si varios estados se comunican entre sí se dice que ellos forman una Clase. Por lo tanto, en el espacio de estados de una Cadena de Markov pueden haber varias clases. Ej: En el ejemplo del jugador existen 3 clases: Clase 1: Estados 1 y 2, Clase 2: Estado 3 y Clase 3: Estado 0.

Clases recurrentes

Una clase es recurrente si no es posible saltar a otra clase a partir de ella. Ej: En el ejemplo del jugador, las clases 2 y 3 son recurrentes. En general, en las clases ó estados recurrentes, la probabilidad de que el proceso habiendo salido de un estado i regrese en cualquier tiempo a ese mismo estado es 1. Las clases 2 y 3 anteriores son tipos especiales de clases recurrentes y se les llama generalmente clases recurrentes absorbentes.

Clases Transitorias

Una clase es transitoria si a partir de ella es posible saltar a otra clase. Ej: En el ejemplo del jugador, la clase 1 es transitoria.

Cadena de Markov Irreducible

Una cadena de markov es irreducible si todos los estados se comunican, formando así una única clase, siendo por tanto ésta una clase recurrente.

Se demuestra que una Cadena Markov sólo puede pasar por un estado transitorio como máximo una cantidad finita de veces. En cambio, si visitamos un estado recurrente, entonces lo visitaremos infinitas veces.

Las clases recurrentes están formadas por estados recurrentes Las clases transitorias están formadas por estados transitorios

Cerrada: Si desde un estado interior no se puede alcanzar ningún estado exterior a la Clase. Un estado absorbente es una clase cerrada con un único estado

Irreducible: Clase cerrada tal que ninguna subclase propia es cerrada. En otros términos, la única clase cerrada es la de todos los estados •Dos estados pertenecen a un mismo conjunto si se comunican • Dos clases deben ser disjuntas, pues si existe algún elemento común, los estados de una clase se puedan comunicar con los de la otra y así resultan de la misma clase

El concepto de comunicación divide el espacio de estados en clase ajenas, es decir, que 2 clases son idénticas o disjuntas Ningún estado puede pertenecer a dos clases distintas

De dos estados que se comunican entres si se dicen que pertenecen a la misma clase

i

i

j k

j i

n n n

j k k

Sólo hay una clase (por transitividad)

Definición Una matriz de una clase se dice irreducible

0

1

2

1/4 1/2

0 12 12 0 P 1 1 2 14 14 2 0 1 2 3 3 0 1 P 2 3

0 1 2 3 1 1 2 2 0 0 1 1 2 2 0 0 1 1 1 1 4 4 4 4 0 0 0 1

1

1/2 1/2

1/4

0

2/3

Sólo hay una clase

2 1/3 1/2

1/2 0

1

Hay tres clases

1/2 1/4

1/4

1/4

1/4 2

3 1

Definición Sea para un estado i, fii la probabilidad de que el proceso regrese al estado i dado que comienza en el estado i

• El estado i se llama recurrente sí fii = 1 • El estado i se llama transitorio sí fii < 1

Un caso especial de un estado recurrente es un estado absorbente sí una vez que se entra en él no se puede abandonar

0

1 2 3 4 0 1 3 4 4 0 0 0 1 1 1 2 2 0 0 0 P 2 0 0 1 0 0 3 0 0 1 2 0 3 3 4 1 0 0 0 0

Ejemplo

1/2

1/2 1 1/4

1 2 1/3

3/4

0

3

1 4

2/3

El estado 2 es un estado absorbente (por lo tanto un estado recurrente), porque una vez que el proceso entra al estado 2 nunca regresará

Los estados 3 y 4 son transitorios porque una vez que el proceso se encuentra en el estado 3, existe una probabilidad positiva de que nunca regresará

Los estados 0 y 1 son recurrentes. Se puede demostrar que f00=1 y f11 = 1. Esto no es sencillo y puede mostrar de la siguiente manera

Observe que la matriz de n pasos es de esta forma, en donde los asteriscos (*) representan números positivos

0 1 P 2 3 4

0 * * 0 0 1

1 * * 0 0 0

2 0 0 1 * 0

3 0 0 0 * 0

4 0 0 0 0 0

Es intuitivamente evidente que el estar en el estado 0 o 1 se regresará a estos mismos Hacer en Excel

Una clase es recurrente si no se puede salir de ella.

Una clase es transitoria si se puede salir de ella y no hay forma de regresar

Definición El periodo de un estado i se define como el entero t (t > 1) si Piin = 0 para todos los valores de n distintos de t, 2t, 3t, /// y t es el entero más grande con esa propiedad

El estado i sólo puede ser visitado en pasos múltiples de t

Ejemplo 0 1 2 0 0 12 12 P 1 1 0 0 2 1 0 0

Realización:

0 1 0

1 0

1 1/2

1/2 1

2

Sólo hay una clase recurrente con período 2

2 0 2 0 1 0 2 0

Siempre se pasa en un número múltiplo de 2

0 P

2

2

0 1 0 0 1 0 12 12 2 0 1 1 2 2

0 P4

1

1

P3

0 1 2 0 0 12 12 1 1 0 0 2 1 0 0

2

0 1 0 0 1 0 12 12 2 0 1 1 2 2

El proceso tiene período 2 P2n+1 = P P2n = P2

PERIODICIDAD DE LAS CLASES RECURRENTES

Para una clase recurrente se puede obtener el período (p) como el máximo común divisor (MCD) de las longitudes de los ciclos que pueden encontrarse en esa clase. Partiendo de la observación de un grafo, un ciclo es una ruta que sale de un estado y regresa a él mismo. Vamos a digerir un poco este concepto con ejemplos...

PERIODICIDAD DE LAS CLASES RECURRENTES

Para determinar el periodo de esta y de cualquier clase recurrente pueden obviares los valores de las probabilidades a los arcos y únicamente observar los ciclos existentes. Las longitudes de dichos ciclos son •Ciclos de longitud 2 (3 – 4 – 3 o 5 – 4 – 5 • Ciclos de longitud 3 (3 – 4 – 5 – 3) MCD (2, 3) = 1, ] el periodo es 1

PERIODICIDAD DE LAS CLASES RECURRENTES

A

B

D

C

En este caso pueden observarse las siguientes longitudes de ciclo

•Ciclos de longitud 2 B – C – B • Ciclos de longitud 4(B – C – D – A – B) •Ciclos de longitud 6(A – B – C – D – C – B – A) MCD (2, 4, 6)= 2 ] Periodo p=2

PERIODICIDAD DE LAS CLASES RECURRENTES

A

B

D

C

En este caso por existir un ciclo de longitud 1 (B – B), el máximo común divisor será de cualquier forma también igual a 1, y por tanto se dice que esta clase recurrente tiene periodo p=1

EJEMPLO DE UNA CADENA PERIÓDICA DE PERIODO K=3

A2

A1

A3

CADENAS ERGÓDICAS a

b 0

c

d 0

e 0 0

Clasificación de estados

1 a 12 2 b 0 14 0 3 4 Q c 0 0 13 0 2 3 d 14 12 0 14 0 e 13 0 13 0 13

Recurrentes

a, c, e

Transitorios

b, d

Periódicos

ninguno

Absorbentes ninguno

1/3

1/4 1/2

b 1/2

a

3/4

d 1/4

1/4

c

1/2

2/3

1/3

1/3

e 1/3

QUE TIPO DE CADENA ES? 1.

2. Irreducible, aperiódica, recurrente y ergódica.

Irreducible, recurrente y periódica de periodo 3. No es ergódica.

3. Irreducible, aperiódica, recurrente y ergódica

QUE TIPO DE CADENA ES? 4.

1

2 5.

4

3

No es irreducible, y por tanto no es de ninguno de los demás tipos. 1 y 4 son recurrentes; 2 y 3 son transitorios

Irreducible, recurrente y periódica de periodo 3. No es ergódica

PERIODICIDAD DE LAS CLASES RECURRENTES Clase recurrente aperiódica: aquella que tenga período p = 1. Clase recurrente periódica: aquella que tenga período p > 1. Cuando una cadena de markov finita homogénea posee una única clase la cual es recurrente aperiódica, se dice que la cadena es ergódica ó totalmente aleatoria. Una cadena de markov finita homogénea es semiergódica si tiene varias clases, entre las cuales pueden haber una o más clases transitorias pero tan solo una clase recurrente aperiodica.

PERIODICIDAD DE LAS CLASES RECURRENTES

• Si hay varias clases recurrentes, todas ellas aperiodicas, se tiene una cadena de markov semiregular. • Si hay una ó varias clases recurrentes, todas ellas periódicas, se tiene una cadena de markov policíclica. • Si hay varias clases recurrentes, algunas periódicas y otras aperiodicas, se tiene una cadena de markov mixta.

ESTADOS ABSORBENTES Y PROBABILIDADES DE ABSORCIÓN El estado k es absorbente si pkk=1 fik: Probabilidad de llegar al estado k dado que en algún momento se encontraba en el estado i Considera todas las probabilidades de la primera transición Considera la probabilidad condicional de absorción al estado k

M

f ik

pij f jk j 0

Sujeta a las condiciones:

f kk f ik

1 0,

si el estadoi es recurrentei k

i

ESTADOS ABSORBENTES Y PROBABILIDADES DE ABSORCIÓN Si se inicia en el estado 2, la probabilidad de perder todo, es decir pasar al estado 0 viene dada por

f 00 1 f10

2 1 f 00 f 20 3 3

f 20

2 1 f10 f 30 3 3

f 30

2 1 f 20 f 40 3 3

f 40 0

f 20

2 2 1 f 20 3 3 3

1 2 1 f 20 (0) 3 3 3

f 20 1 / 5 0

1

2

3

4

0

1

0

0

0

0

1

2/3

0

1/3

0

0

2

0

2/3

0

1/3

0

3

0

0

2/3

0

1/3

4

0

0

0

0

1

ESTADOS ABSORBENTES Y PROBABILIDADES DE ABSORCIÓN Si se inicia en el estado 2, la probabilidad de ganar todo, es decir pasar al estado 4 viene dada por

f 04 0 f14

2 1 f04 f 24 3 3

f 24

2 1 f14 f 34 3 3

f 34

2 1 f 24 f 44 3 3

f 44 1

f 24

2 1 f 24 3 3

1 2 1 f 24 3 3 3

f24 1 / 5

PROBABILIDADES DE ESTADO ESTABLE Es de interés ahora conocer la probabilidad de hallar el sistema en un estado determinado cuando lleva evolucionando el proceso un tiempo indefinidamente largo. A tales probabilidades se les denomina probabilidad de estado estable. El estudio de las probabilidades de estado estable se entiende por tanto como el estudio del comportamiento a largo plazo de las Cadenas de Markov. A las probabilidades estacionarias se les simboliza como πj

P=

0.080 0.632 0.264 0.080

0.184 0.368 0.368 0.184

0.368 0.000 0.368 0.368

0.368 0.000 0.000 0.368

(8)

P* = P =

π0

π1

0.286 0.286 0.286 0.286

0.285 0.285 0.285 0.285

π2

0.264 0.264 0.264 0.264

π3

0.166 0.166 0.166 0.166

CONCEPTO DE ERGODICIDAD DE BOLTZMAN Ejemplo de ergodicidad comentado por Caldentey y Mondschein de la Universidad de Chile. Supongamos que disponemos de dos estanques A y B unidos por una tubería, la que contiene una llave de paso originalmente cerrada. un equilibrio se alcanza

el estado final que ha alcanzado el sistema es independiente de las condiciones iniciales

El estanque A contiene oxigeno a una presión Pa y el B helio a una presión Pb. Si la válvula se abre las moléculas de oxigeno evolucionan hacia el estanque B, mientras que las de helio lo hacen hacia el estanque A.

CÁLCULO DE PROBABILIDADES ESTACIONARIAS Forma 1 de Calculo

Multiplicando por si misma a la Matriz inicial de Probabilidades de Transición, hasta que la matriz resultante después de muchas transiciones se estabilice en unos valores de probabilidad definidos.

Forma 2 de Calculo

Empleando el simple concepto de Probabilidad Total

P(A) = P(A) P(A/A)+P(B) P(A/B) + P(C) P(A/C) + P(D) P(A/D) + … π0 = π0 poo + π1 p1o + π2 p2o + π3 p3o π1 = π0 po1 + π1 p11 + π2 p21 + π3 p31 π2 = π0 po2 + π1 p12 + π2 p22 + π3 p32 π3 = π0 po3 + π1 p13 + π2 p23 + π3 p33 π0 + π1 + π2 + π3 =1

M j

i

pij

i 0

M i i 0

1

j

CÁLCULO DE PROBABILIDADES ESTACIONARIAS

P=

0.080 0.632 0.264 0.080

0.184 0.368 0.368 0.184

0.368 0.000 0.368 0.368

0.368 0.000 0.000 0.368

π0 = 0.286

π1 = 0.285

π2 = 0.264

π3 = 0.166

CÁLCULO DE PROBABILIDADES ESTACIONARIAS Con las probabilidades estacionarias ya calculadas, puede calcularse el tiempo de la primera recurrencia de un estado, es decir, el tiempo de que un estado i vuelva a ese mismo estado por primera vez. A estos tiempos suelen denominarse tiempos de primera pasada y se simbolizan por μjj.

1 jj j

El caso de la movilidad de clases sociales. Suponga

que

en

la

sociedad

sólo

existen

los

estratos

económicos Alto, Medio y Bajo

A continuación se muestra la matriz de transición de un

paso,

es

decir

la

probabilidad de pasar en una generación de una

clase social a otra

Estado 0 Clase Alta Estado 1 Clase Media Estado 2 Clase Baja

Hijos A M B A 0.45 0.48 0.07 P M 0.05 0.7 0.25 B 0.01 0.5 0.49

Por ejemplo, el 1% de las personas que tuvieron padres de clase Baja logran ser personas de clase Alta

Recordar que

= P

0.45 0.48 0.07 * 0.05 0.7 0.25 0.01 0.5 0.49 Las ecuaciones del estado estable

B

P A PAM A PAB

A

M

A M

A AA

B

PMA M PMM M PMB 1

M

P

B BA

P B PBB

B BM