Cadenas de Markov

Ingeniería en Ciencias Económicas y Financieras

Proceso estocástico:

• Es un conjunto o sucesión de variables aleatorias: {Xt}

definidas en un mismo espacio de probabilidad.• Normalmente el índice t ϵT representa un tiempo y Xt el

estado del proceso estocástico en el instante t.• El proceso puede ser de tiempo discreto o continuo si T esdiscreto o continuo. (Un proceso estocástico es de tiempo

continuo si el estado del sistema se revisa en cualquier tiempo)

• Si el proceso es de tiempo discreto, usamos enteros pararepresentar el índice: {X0, X1, ...}

Ejemplos de procesos estocásticos:

1. Serie mensual de ventas de un producto2. Estado de una máquina al final de cada semana

(funciona/averiada)3. Nº de clientes esperando en una cola cada 30 segundos4. Marca de detergente que compra un consumidor cada vez

que hace la compra. Se supone que existen 7 marcas diferentes

5. Número de unidades en inventario al finalizar la semana

Introducción

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, etc.

1. Definición de Cadena de Markov

• Una Cadena de Markov (CM) es:• Un proceso estocástico• Con un número finito de estados (M+1)• Con probabilidades de transición

estacionarias• Que tiene la propiedad markoviana

– Un conjunto finito de M+1 estados, exhaustivos y mutuamente excluyentes

– Ciclo de markov (“paso”) : periodo de tiempo que sirve de base para examinar las transiciones entre estados (ejemplo: un mes, una semana, un año, etc)

– Probabilidades de transición entre estados, en un ciclo (matriz P)

– Distribución inicial del sistema entre los M+1 estados posibles

ELEMENTOS DE UNA CADENA DE MARKOV

Cadenas de Markov

Un proceso estocástico tiene la propiedad markoviana si las probabilidades de transición en un paso sólo dependen del estado del sistema en el período anterior (memoria limitada o falta de memoria)

• Propiedad markoviana: “Probabilidad condicional de cualquier evento futuro dado cualquier evento pasado y siendo el estado actual Xt=i, es independiente de cualquier estado pasado y solo depende del estado actual del proceso”

• Probabilidades Estacionarias: “Las probabilidades de transición no cambian con el tiempo”

Cadenas de Markov y matriz de transición a n pasos

Se debe satisfacer:

• pij(n)≥0 para toda i y toda j, n=0, 1, 2• Se asumirá que se conocen las probabilidades iniciales P{X0=i} para toda i.

Cadenas de Markov

Ejemplos:

• Comportamiento (sube/baja) del precio de las acciones hoy depende de lo ocurrido ayer

• Problema de la ruina de un jugador de casino

Otro ejemplo(Hillier&Liebermann):

Ecuaciones de Chapman-Kolmogorov

Casos especiales:

Si m=1

Si m=n-1

La matriz de transición a n pasos se puede obtener de la siguiente

manera:

Ejemplo:1. En el ejemplo de inventarios visto inicialmente encuentre :

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

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

c. Dado que queda una cámara al final de una semana, la probabilidad de que no hayan cámaras en inventario 4 semanas más tarde.

Un caso práctico:• Un estudio realizado por el INEC: Proyecto

de matrices de transición laboral

Pregunta del estudio: ¿cuántas personas trabajan en su

establecimiento?

Probabilidades incondicionales del estado

• Las probabilidades de transición de uno o n pasos son probabilidades condicionales.

• Si se desea la probabilidad incondicional P{Xn}=j, es necesario especificar la distribución de probabilidad del estado inicial, o sea P{X0=i}, para i=0, 1, … ,M. Entonces

P{Xn=j}=P{X0=0}p0j(n)+P{X0=1}p1j

(n)+…+P{X0=M}pMj(n)

• En el ejemplo de inventarios, se supuso que se tenían tres unidades en inventario. Encuentre la probabilidad incondicional de que hayan tres cámaras en inventario dos semanas después de que el sistema se puso en marcha.

Clasificación de estados de una cadena de Markov

• Los estados de las cadenas de Markov, se clasifican de acuerdo a las propiedades de sus probabilidades de transición.

Se dice que el estado j es accesible desde el estado i si pij

(n)>0, para alguna n ≥0.

Se dice que los estados i y j se comunican, si el estado j es accesible desde el estado i y el estado i es accesible desde el estado j.

• De manera general

1. Cualquier estado se comunica consigo mismo

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

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.

• Como consecuencia de estas propiedades de comunicación, se puede hacer una partición del espacio de estados en clases ajenas, en las cuales, dos estados que se comunican pertenecen a una misma clase. Si existe solo una clase, es decir todos los estados se comunican, se dice que la cadena de Markov es irreducible.

Ejemplos:

• Encuentre las clases ajenas en el ejemplo de acciones y en el ejemplo de la ruina del jugador de casino.

• Un estado se llama transitorio si, después de haber entrado a este estado, el proceso nunca regresa a él, es decir un estado es transitorio si y solo si existe un estado j (j≠i) que es accesible desde el estado i, pero no viceversa, esto es, el estado i no es accesible desde el estado j.

• Se dice que un estado es recurrente si, después de haber entrado a este estado, el proceso definitivamente regresará a ese estado. Un estado es recurrente si y solo si no es transitorio.

• Un tipo especial de estado recurrente es aquel estado al cual el proceso una vez que entró en él nunca saldrá de este estado, este tipo de estado se dice absorbente. Por lo tanto, el estado i es absorbente si y solo si pii=1

• La recurrencia es una propiedad de clase, es decir, todos los estados de una clase son recurrentes o transitorios.

• El periodo de un estado i se define como el entero t (t>1) si pii(n)=0 para todos los valores de n distintos de t, 2t, 3t, … y t es el entero más grande con esta propiedad.

Propiedades a largo plazo de las cadenas de Markov

• Existe una probabilidad límite de que el sistema se encuentre en el estado j después de un número grande de transiciones, y esta propiedad es independiente del estado inicial.

• Para una cadena de Markov irreducible ergódica

• Donde las πj satisfacen de manera única las siguientes ecuaciones de estado estable:

• Los valores πj reciben el nombre de probabilidades de estado estable.

Cadenas de MarkovProblema del Ratón:

Un ratón cambia de habitación cada minuto con igual probabilidad a las salas adyacentes, se asume que inicialmente está en la entrada

Sala

Habitación Cocina

En

trad

a

Matriz de probabilidades de transición :

0 1/3 1/3 1/3

1/2 0 1/2 0

1/3 1/3 0 1/3

1/2 0 1/2 0

P =

S

E

C

H

S E C H

S E

H C

1/2

1/2

1/2

1/2

1/3

1/3

1/3

1/3

1/3

1/3

Tiempos de primera pasada

Con mucha frecuencia es importante poder hacer afirmaciones en términos de probabilidad sobre el número de transiciones que hace el proceso al ir del estado i al estado j por primera vez. Este lapso recibe el nombre de tiempo de primera pasada al ir del estado i al estado j. Cuando j=i, este tiempo de primera pasada se denomina tiempo de recurrencia para el estado i.

Tiempo esperado de primera pasada

Siempre que satisface de manera única la ecuación

La cual da origen a un sistema de ecuaciones.

Cuando i=j, los tiempos de recurrencia, se obtienen utilizando

las probabilidades de estado estable. Así,

Calcular el tiempo esperado hasta que el ratón ingrese a la habitación por primera vez, dado que inicialmente se

encuentra en la entrada.

Si S=0, E=1, C=2 y H=3

Buscamos µ13, para esto planteamos el siguiente sistema de ecuaciones:

Así dado que queremos averiguar µ13 debemos resolver el sistema

jiitodaparap kjjk

ikij

,1

23221321032023

23121311031013

23021301030003

1

1

1

ppp

ppp

ppp

Es decir:

23130323

23130313

23130303

03/13/11

2/102/11

3/13/101

Resolviendo el sistema se tiene

4

5

4

23

13

03

Las probabilidades de estado estable son:

Por tanto los tiempos medios de recurrencia son:

200.0

275.0

200.0

325.0

3

2

1

0

5

63.3

5

07.3

33

22

11

00