Upload
others
View
24
Download
0
Embed Size (px)
Citation preview
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.