Cadenas de Markov

Absorbentes

Dr. José Dionicio Zacarias Flores

Estas diapositivas tienen como fuente de apoyo bibliográfico principalmente de los libros:

John G. Kemeny y J. Laurie Snell. (1981) Finite Markov Chains. Springer-Verlag.

Introducción

▪ Si un estado es el único elemento de un

conjunto ergódico, entonces se le llama

estado absorvente. Es decir, pii = 1.

▪ Una cadena, cuyos estados no transitorios

son absorbidos, se llama cadena absorbente.

Teorema 1

En cualquier CM, no importando donde inicie el

proceso, la probabilidad después de n pasos de

que el proceso se encuentre en un estado

ergódico, tiende a uno, cuando n tiende a

infinito.

Demostración

Si el proceso alcanza una vez un estado ergódico, entonces nunca

puede abandonar su clase de equivalencia, de aquí que en

futuros pasos, siempre estará en un estado ergódico.

Supongamos que se inicia en un estado transitorio, entonces su

clase de equivalencia no es minimal, de aquí que hay un elemento

minimal debajo de él. Esto significa que se puede alcanzar un

conjunto ergódico.

Demostración

Supongamos entonces que desde cualquier estado transitorio es posiblealcanzar un estado ergódico en no más de n pasos. Como hay sólo un númerofinito de estados, n es simplemente el número máximo de pasos requeridos paracualquier estado. De aquí que hay un número positivo p tal que la probabilidadde entrar a un estado ergódico en a lo más en n pasos es al menos p, desdecualquier estado transitorio.

Por lo que la probabilidad de no alcanzar un estado ergódico en n pasos es a lomás (1-p) <1.

La probabilidad de no alcanzar un estado ergódico en kn pasos, es menor oigual que (1-p)k, y esta probabilidad tiende a cero cuando k tiende a infinito.

Conclusión: se alcanza un estado ergódico en n pasos. #

Corolario

Hay números b > 0 y 0 < c <1 tal que 𝑝𝑖𝑗(𝑛)

b· cn,

para cualesquiera estados transitorios si, sj.

Demostración. Se deja como ejercicio. #

Idea: Muestra la tasa a la que que 𝑝𝑖𝑗(𝑛)

→ 0

Consideraciones

Es conveniente presentar a la CM en una versión integrada. Para

esto uniremos a todos los conjuntos ergódicos, y a todos los

conjuntos transitorios. Supongamos que hay s estados transitorios, y

r-s estados ergódicos. Entonces la forma de la nueva matriz es:

Consideraciones

Donde la región O consiste de puros ceros. La submatriz

Qs x s se refiere al proceso siempre que permanezca en

estados transitorios, la submatriz Rs x (r-s) se refiere a la

transición de estados transitorios a ergódicos, y la

submatriz S(r-s) x (r-s) trata el proceso una vez que ha

alcanzado un conjunto ergódico.

Por el teorema 1, las potencias de Q tienden a

cero. Y cuando en P sus potencias van creciendo,

las matrices resultantes se aproximan a una matriz

cuyas últimas s columnas son todas cero.

Ahora, si la CM es absorbente, la submatriz S resulta

ser la submatriz Iidentidad Ir-s)x(r-s). Por lo que la forma

canónica es:

Conclusión

Otra vez el teorema 1 nos dice que cuando P sea

elevada a potencias la matriz I permanecerá

siendo la matriz identidad, lo que significa que

llegará un momento en que la CM entrará a un

estado absorbente y será absorbida.

Ejemplo 1

Supongamos el siguiente proceso estocástico

𝑠1 𝑠2 𝑠3 𝑠4 𝑠5

•-----•-----•-----•-----•

Suponiendo que si el proceso alcanza los estados s1 o s5,

permanecerá ahí indefinidamente, su matriz de transiciones será:

Ejemplo 1

¿Cuál es la matriz en su forma canónica?

Ejemplo 1

Forma canónica

Ejemplo 2

Recordando el ejemplo de la urna con 2 bolas

inicialmente sin pintar, cuya matriz de transiciones es:

¿Cuál es su forma canónica?

La CM no tiene estados absorbentes,

pero si un conjunto ergódico

formado por los 3 primeros estados.Nos puede interesar estudiar la CM

sólo hasta que entre al conjunto

ergódico, podemos hacer

absorbentes a los estados ergódicos.

Ejemplo 2

Forma canónica

Ejemplo 2

Si ni siquiera nos importa en qué estado se ingresa al

conjunto ergódico, podemos agrupar los estados

ergódicos en uno solo, obteniendo así una matriz más

simple:

La matriz fundamental

Teorema 2

Para cualquier cadena de Markov absorbente, I-Q tiene

una inversa, y

(𝐼 − 𝑄)−1= I + Q + 𝑄2 + ⋯ = σ𝑘=0∞ 𝑄𝑘

Soporte del teorema

Si An tiende a O (matriz cero) cuando n tiende a infinito,

entonces (I-A) tiene una inversa, y

(𝐼 − 𝐴)−1= I + A + 𝐴2 + ⋯ = σ𝑘=0∞ 𝐴𝑘

Definición

Para una CM absorbente definimos a la

matriz fundamental como N = (I-Q)-1.

Definición

Definimos nj a ser la función que nos da el número total de veces en que el proceso está en sj. (esto tiene sentido sólo para estados transitorios sj) 𝑢𝑗𝑘 se define como la función que es 1 si el proceso está en estado sj

después de k pasos, y de lo contrario es 0, es decir:

𝑢𝑗𝑘 = ቊ

1 𝑠𝑖 𝑒𝑙 𝑝𝑟𝑜𝑐𝑒𝑠𝑜 𝑒𝑠𝑡á 𝑒𝑛 𝑒𝑙 𝑒𝑠𝑡𝑎𝑑𝑜 𝑠𝑗 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑘 𝑝𝑎𝑠𝑜𝑠

0 𝑠𝑖 𝑠𝑢𝑐𝑒𝑑𝑒 𝑜𝑡𝑟𝑎 𝑐𝑜𝑠𝑎

A continuación le daremos una interpretación probabilística a N.

Teorema

𝐸𝑗 𝑛𝑗 = 𝑁 , donde si, sj T. Donde T es el conjunto de

estados transitorios.

Nota. Este resultado lo que nos dice es que la media del

número total de veces en que el proceso está en un

estado transitorio dado es siempre finito. Y que ese valor

es N. Note que 𝑛𝑗 = σ𝑘=0∝ 𝑢𝑗

𝑘

Ejemplo 3

Retomando el ejemplo 1 de estas diapositivas, (I-Q) es:

e

Y de aquí

𝑃 =

1 0 ⋮0 1 ⋮⋯ ⋯ ⋮

0 0 00 0 0⋯ ⋯ ⋯

𝑞 0 ⋮0 0 ⋮0 𝑝 ⋮

0 𝑝 0𝑞 0 𝑝0 𝑞 0

Entonces →

← Q

Como p+q = 1, (p+q)2 = 1, de

donde 1-2pq = p2+q2.

Tarea

Supongamos que un estudiante que va a una determinada universidad tiene cada año

una probabilidad p de fracasar, una probabilidad q de tener que repetir el año, y una

probabilidad r de pasar al año siguiente. Formamos una cadena de Markov, tomando

como estados s1 es suspendido, s2 se ha graduado, s3 es un Senior, s4 es un Junior, s5 es un

estudiante de segundo año, s6 es un estudiante de primer año. Su matriz de transición es:

Tarea

Encontrar (I-Q), y N, e interpretar el resultado. Para el caso

específico donde p = .2, q = .1, r = .7, calcular lo anterior e

interpretar.

Aplicaciones de la Matriz

Fundamental

Introducción

Existen algunas cantidades de interés que pueden ser expresadas

en términos de la matriz fundamental

Definición

A continuación definiremos nuevas matrices y vectores:

N2 = N(2Ndg - I) – Nsq matriz s x s

B = NR matriz s x (r-s)

𝜏 = 𝑁 vector columna con s componentes

𝜏2 = (2N – I) 𝜏 - 𝜏q vector columna con s componentes

Teorema

QN = NQ = N – IDemostración.

Recordar que:

Entonces si multiplicamos a N por la derecha o por la izquierda

De donde se ve que es la misma expresión inicial pero sin I #

𝑁 = (𝐼 − 𝑄)−1 = I + Q + 𝑄2 + ⋯ (∗)

QN = NQ = Q + 𝑄2 + 𝑄3 + ⋯

Teorema

𝑉𝑎𝑟𝑗 𝑛𝑗 = 𝑁2, 𝑑𝑜𝑛𝑑𝑒 𝑠𝑖 𝑦 𝑠𝑗 ∈ 𝑇.

Demostración. Se omite. #

Ejemplo

Si en el ejemplo 3, tomamos p = 2/3.

Ejemplo

Esto nos muestra que

sin importar con que

estado se inicie, la

varianza es más

grande para el estado

que está en medio.

Además N2 es bastante grande en

comparación con Nsq;

por lo tanto, las medias

son estimaciones poco

confiables para esta cadena de Markov.

Definición

Sea t la función que indica el número de pasos (incluyendola posición original) en los que el proceso se encuentra enun estado transitorio.

Notas. Si el proceso inicia en un estado ergódico, entoncest = 0. si el proceso inicia en un estado transitorio, t nos da elnúmero total de pasos necesarios para alcanzar unconjunto ergódico.

En una cadena absorbente, es el tiempo de absorción.

Teorema

Ei[t] = ; Vari[t] = 2, donde si T.

Comentarios para una demostración

t se define como 𝑡 = σ𝑠𝑗 ∈𝑇𝑛𝑗. Ei[t] = σ𝑠𝑖 ∈𝑇

𝐸𝑖 𝑛𝑗 = N.

En nuestro ejemplo anterior,

por lo que

Vemos que se espera alcanzar el límite más rápidamente desde s4.

Esto no es sorprendente, ya que es más fácil alcanzar el límite

desde un estado exterior que desde el medio, y es más probable

que el proceso se mueva hacia la derecha. Pero nuevamente

observamos que la varianza es considerable.

Hemos calculado medias solo para medidas en las que el proceso

comienza en un estado dado si. Pero es fácil obtener a partir de

esto las medias y las varianzas para un vector de probabilidad

inicial arbitrario.

Corolario

Si es el vector de probabilidad inicial para una cadena

absorbente, y ’ consiste de las últimas s componentes

de , es decir ’ nos da las probabilidades iniciales para los estados transitorios, entonces

E[nj] = ’ N Var[nj] = ’ N(2Ndg-I) – (’ N)sq

E[t] = ’ Var[t] = ’ (2N-I) - (’ )sq.

Teorema

NOTA. Aquí nos referimos a la cuestión de qué estado de

absorción es probable que capture el proceso.

Si bij es la probabilidad de que el proceso que comienza

en el estado transitorio si termina en el estado absorbente

sj, entonces

{bij} = B = NR, si T, sj T.

Ejemplo

Tomando el ejemplo de esta sección:

Problemas de cadenas

abosorbentes

Problema 1

Poner las siguientes matrices en la forma canónica para cadenas absorbentes.

Problema 2

Aplicar el Teorema 1 de estas diapositivas a una cadena

de Markov absorbente con un solo estado absorbente.

Problema 3

Aplicar el resultado del ejercicio anterior a una cadena

ergódica en la cual un estado se convierte en absorbente,

es decir, supongamos que el i-ésimo estado se vuelve

absorbente reemplazando la i-ésima fila en la matriz de

transición por una fila con un 1 en la i-ésima componente.

Problema 4

Calcular la matriz fundamental para la cadena absorbente con matriz de transición.

Problema 5

Calcular la matriz fundamental para la siguiente

cadena absorbente con matriz de transición, con c = 0

y d 0, e interpretar el resultado.

Problema 6

Demostrar que si la matriz fundamental N es dada

para una cadena absorbente, entonces N-1 existe y

Q = I – N-1.

Problema 7

Demostrar que si la matriz fundamental N es dada

para una cadena absorbente, entonces N-1 existe y

Q = I – N-1.

Problema 8

Probar que NQ = N – I. después comprobar el resultado en:

Problema 9

Si una cadena absorbente tiene solo un estado absorbente, ¿Qué

puede decirse acerca de la matriz B? En la siguiente matriz, hacer

R un estado obsorbente, calcular N y B, y verifica el enunciado.

Problema 10

Cambiar la siguiente matriz de transición en una cadena

absorbente asumiendo que el proceso se para si un 0 o

un 9 es alcanzado. Construir la nueva matriz de transición,

en forma canónica. Después calcular N, N2, B, , 2.