Cadenas de Markov reversibles

ICI3017 Modelos Estoc´sticos * Cadenas de Markov reversibles
a
Considere una cadena de Markov homog´nea que ha estado por mucho tiempo en operaci´n hasta alcanzar su dise
otribuci´n estacionaria, con probabilidades de transici´n Pij y probabilidades estacionarias πi
o
o
Qij

=
=
=
=

P(Xn = j|Xn+1 = i)
P(Xn = j, Xn+1 = i)
P(Xn+1 = i)
P(Xn+1 = i|Xn= j)P(Xn = j)
P(Xn+1 = i)
Pji πj
πi

Se dice que una cadena de Markov es reversible en el tiempo si se cumple Pij = Qij , ∀i, j lo que equivale a
∀i, j

πi Pij = πj Pji ,(1)

Notemos que la ecuaci´n (1) es una condici´n m´s fuerte que la existencia de una distribuci´n estacionaria:
o
o
a
o
πi Pij =
i

πj Pji = πj

Pji = πj ,

i

∀j

iSi encontramos valores {xi ≥ 0 : i xi = 1} que satisfacen la ecuaci´n (1), entonces estos valores representan las
o
probabilidades estacionarias para los distintos estados.Problemas
1. Un caballo de ajedrez markoviano: ¿Cu´l es el n´mero esperado de pasos que debe hacer un caballo para volver
a
u
a su misma casilla en caso que est´ en una esquina?
e
2.Un rat´n markoviano: ¿Cu´l es porcentaje de veces en el largo plazo que el rat´n estar´ en su habitaci´n si est´
o
a
o
a
o
a
en una esquina en un laberinto de 3 × 3? ¿Y en unode 20 × 30?
3. Caminata markoviana en un grafo: Sea un gr´fo conexo G = (V, A) como el de la figura 1. ¿Cu´l es el n´mero
a
a
u
esperado de pasos que debe tomar una caminataaleatoria para volver al nodo original?
4. Caminata markoviana en un grafo con pesos: Considere el problema 3, pero con probabilidades de transici´n
o
wij
Pij =
j wij

Figura 1: Ungrafo conexo con pesos

Vemos que 1 y 2 son un caso particular de 3, y ´ste es un caso particular de 4. Son cadenas de Markov reversibles con
e
j

πi =
i

wij
j

wij