10.4: Cadenas absorbentes de Markov

Objetivos de aprendizaje

En esta sección, aprenderás a:

1. Identificar estados absorbentes y cadenas absorbentes de Markov
2. Resuelve e interpreta cadenas absorbentes de Markov.

En esta sección, estudiaremos un tipo de cadena de Markov en la que cuando se alcanza cierto estado, es imposible salir de ese estado. Tales estados se llaman estados absorbentes, y una Cadena de Markov que tiene al menos uno de esos estados se llama una cadena Absorbente de Markov.

Supongamos que tiene la siguiente matriz de transición.

El estado _S2 es un estado absorbente, porque la probabilidad de pasar del estado _S2 al estado _S2 es 1. Lo cual es otra forma de decir que si estás en el estado S ₂, permanecerás en el estado S ₂.

De hecho, esta es la forma de identificar un estado absorbente. Si la probabilidad en fila\(i\) y columna\(i\),\(p_{ii}\), es 1, entonces el estado S _i es un estado absorbente.

Ejemplo\(\PageIndex{1}\)

Considere las matrices de transición A, B, C para las cadenas de Markov que se muestran a continuación. ¿Cuál de las siguientes cadenas de Markov tiene un estado absorbente?

\ [A=\ left [\ begin {array} {lll}
.3 & .7 & 0\\
0 & 1 & 0\\
.2 & .3 & .5
\ end {array}\ derecha]\ quad B=\ left [\ begin {array} {lll}
0 & 1 & 0\\ 0 &
0 & 0 & 1\\
1 & 0 & 0
\ end {array}\ right]\ quad C=\ left [\ begin {array} {cccc}
.1 & .3 & .4 & .2\\
0 & .2 & .1 & .7\\
0 & 0 & 0 & 0 &
0 & 0 & 0 & 1
\ end {array}\ derecha]\ nonumber\]

Solución

tiene S ₂ como estado absorbente.

Si estamos en el estado S ₂, no podemos dejarlo. Del estado S ₂, no podemos hacer la transición al estado S ₁ o S ₃; las probabilidades son 0.
La probabilidad de transición del estado _S2 al estado _S2 es 1.

no tiene ningún estado absorbente.

Desde el estado S ₁, siempre hacemos la transición al estado _S2. Del estado S ₂ siempre hacemos la transición al estado S ₃. Del estado S ₃ siempre hacemos la transición al estado S ₁. En esta matriz, nunca es posible permanecer en el mismo estado durante una transición.

tiene dos estados absorbentes, S ₃ y S ₄.

Desde el estado S ₃, solo puedes permanecer en el estado S ₃, y nunca hacer la transición a ningún otro estado. De manera similar desde el estado S ₄, solo puede permanecer en el estado S ₄, y nunca hacer la transición a ningún otro estado.

Resumimos cómo identificar estados absorbentes.

Resumen

Un estado S es un estado absorbente en una cadena de Markov en la matriz de transición si

• La fila para el estado S tiene uno 1 y todas las demás entradas son 0

Y

• La entrada que es 1 está en la diagonal principal (fila = columna para esa entrada), indicando que nunca podremos salir de ese estado una vez ingresada.

A continuación definimos una cadena de Markov absorbente

Cadena Absorbente de Markov

Una cadena de Markov es una cadena de Markov absorbente si

• Tiene al menos un estado absorbente

Y

• Desde cualquier estado no absorbente en la cadena de Markov, es posible eventualmente pasar a algún estado absorbente (en una o más transiciones).

Ejemplo\(\PageIndex{2}\)

Considere las matrices de transición C y D para las cadenas Markov que se muestran a continuación. ¿Cuál de las siguientes cadenas de Markov es una cadena de Markov absorbente?

\ [\ mathrm {C} =\ left [\ begin {array} {llll}
.1 & .3 & .4 & .2\
0 & .2 & .1 & .7\\
0 & 0 & 0 & 1 & 0 &
0 & 0 & 0 & 0 & 1
\ end {array}\ derecha]\ quad\ mathrm {D} =\ left [\ begin {array} {lllll}
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
.2 & .2 & .2 & .2 & .2\\
0 & 0 & 0 & 0 & 0 & 0 & .3 & .7\
0 & 0 & 0 & 0 & .6 & .4
\ end {array}\ derecho]\ nonumber\]

Solución

C es una cadena de Markov absorbente pero D no es una cadena de Markov absorbente.

La matriz C tiene dos estados absorbentes, S ₃ y S ₄, y es posible llegar al estado S ₃ y _S4 desde S ₁ y _S2.

La matriz D no es una cadena de Markov absorbente. Tiene dos estados absorbentes, S ₁ y _S2, pero nunca es posible llegar a ninguno de esos estados absorbentes desde S ₄ o S ₅. Si se encuentra en el estado S ₄ o S _5, siempre permanece en transición entre los estados S ₄ o S _5m y nunca podrá ser absorbido en ninguno de los estados _S1 o _S2

En el resto de esta sección, examinaremos la absorción de las cadenas de Markov con dos problemas clásicos: el problema de la caminata del borracho aleatorio y el problema de la ruina del jugador. Y finalmente concluiremos con un modelo absorbente de Markov aplicado a una situación del mundo real.

Caminata Aleatoria de Borracho

En este ejemplo examinamos brevemente las ideas básicas sobre la absorción de las cadenas de Markov.

Ejemplo\(\PageIndex{3}\)

Un hombre camina por una porción de tres cuadras de Main St. Su casa se encuentra en un extremo de la sección de tres cuadras. Una barra está en el otro extremo de la sección de tres bloques. Cada vez que llega a una esquina al azar o va adelante una cuadra o da la vuelta y retrocede una cuadra. Si llega a casa o al bar, se queda ahí. Los cuatro estados son Inicio (H), Esquina 1 (C ₁), Esquina 2 (C ₂) y Bar (B).

Escribe la matriz de transición e identifica los estados absorbentes. Encuentra las probabilidades de terminar en cada estado absorbente dependiendo del estado inicial.

Solución

La matriz de transición se escribe a continuación.

El hogar y el Bar están absorbiendo estados. Si el hombre llega a casa, no se va. Si el hombre llega al bar, no se va. Ya que es posible llegar a casa o al bar de cada una de las otras dos esquinas en su caminata, esta es una cadena absorbente de Markov.

Podemos elevar la matriz de transición T a una potencia alta,\(n\). Una encontramos una potencia T ⁿ que permanece estable, nos dirá la probabilidad de terminar en cada estado absorbente dependiendo del estado inicial.

T ⁹¹ = T ⁹⁰; la matriz no cambia a medida que continuamos examinando potencias superiores. Vemos que a la larga, la cadena de Markov debe terminar en un estado absorbente. A la larga, el hombre debe terminar eventualmente ya sea en su casa o en el bar.

La segunda fila nos dice que si el hombre está en la esquina C ₁, entonces hay un 2/3 de posibilidades de que termine en casa y un 1/3 de oportunidad terminará en el bar.

La tercera fila nos dice que si el hombre está en la esquina C ₂, entonces hay una probabilidad de 1/3 de que termine en casa y una probabilidad de 2/3 terminará en el bar.

Una vez que llega a su casa o al bar, nunca sale de ese estado absorbente.

Obsérvese que si bien la matriz T ⁿ para suficientemente grande se\(n\) ha vuelto estable y no está cambiando, no representa una matriz de equilibrio. Las filas no son todas idénticas, como encontramos en las cadenas regulares de Markov que alcanzaron un equilibrio.

Podemos escribir una “matriz de solución” más pequeña conservando solo filas que se relacionan con los estados no absorbentes y conservando solo las columnas que se relacionan con los estados absorbentes.

Entonces la matriz de solución tendrá las filas _C1 y _C2, y las columnas H y B. La matriz de solución es

La primera fila de la matriz de solución muestra que si el hombre está en la esquina C ₁, entonces hay una probabilidad de 2/3 de que termine en casa y una probabilidad de 1/3 terminará en el bar.

La segunda fila de la matriz de solución muestra que si el hombre está en la esquina C ₂, entonces hay una probabilidad de 1/3 de que termine en casa y una probabilidad de 2/3 terminará en el bar.

La matriz de solución no muestra que eventualmente haya 0 probabilidades de terminar en C1 o C2, o que si comienzas en un estado absorbente H o B, te quedes ahí. La matriz de soluciones más pequeña supone que entendemos estos resultados y no incluye esa información.

El siguiente ejemplo es otro ejemplo clásico de una cadena de Markov absorbente. En el siguiente ejemplo examinamos más detalles matemáticos detrás del concepto de la matriz de solución.

Problema de ruina de Gamber

Ejemplo\(\PageIndex{4}\)

Un jugador tiene $3,000, y decide apostar $1,000 a la vez en una mesa de Black Jack en un casino de Las Vegas. Ella se ha dicho a sí misma que seguirá jugando hasta que se vaya a la quiebra o tenga $5,000. Su probabilidad de ganar en Black Jack es de .40. Escriba la matriz de transición, identifique los estados absorbentes, encuentre la matriz de solución y determine la probabilidad de que el jugador se arruine financieramente en una etapa en la que tenga $2,000.

Solución

La matriz de transición se escribe a continuación. Claramente el estado 0 y el estado 5K son los estados absorbentes. Esto tiene sentido porque en cuanto la jugadora llega a 0, ella está arruinada financieramente y el juego termina. De igual manera, si la jugadora alcanza los 5.000 dólares, se ha comprometido a renunciar y, nuevamente, el juego ha terminado. El lector debe señalar que p ₀₀ = 1, y p ₅₅ = 1.

Observe además que dado que la jugadora apuesta solo $1,000 a la vez, puede subir o bajar su dinero solo en $1,000 a la vez. Es decir, si tiene $2,000 ahora, después de la siguiente apuesta puede tener $3,000 con una probabilidad de .40 y $1,000 con una probabilidad de .60.

Para determinar la tendencia a largo plazo, elevamos la matriz a potencias superiores hasta que todos los estados no absorbentes sean absorbidos. Esta es la llamada matriz de solución.

La matriz de solución a menudo se escribe en la siguiente forma, donde los estados no absorbentes se escriben como filas en el lateral, y los estados absorbentes como columnas en la parte superior.

La tabla enumera las probabilidades de ser absorbido en el estado 0 o estado 5K a partir de cualquiera de los cuatro estados no absorbentes. Por ejemplo, si en algún caso el jugador tiene $3,000, entonces su probabilidad de ruina financiera es 135/211 y su probabilidad de llegar a 5K es 76/211.

Ejemplo\(\PageIndex{5}\)

Resuelve el problema de la ruina del jugador del ejemplo\(\PageIndex{4}\) sin elevar la matriz a potencias superiores, y determinar el número de apuestas que hace el jugador antes de que termine el juego.

Solución

Al resolver estados absorbentes, a menudo es conveniente reorganizar la matriz para que las filas y columnas correspondientes a los estados absorbentes se enumeren primero. A esto se le llama la forma canónica. La matriz de transición del Ejemplo 1 en la forma canónica se enumera a continuación.

La forma canónica divide la matriz de transición en cuatro submatrices como se indica a continuación.

A la matriz\(F = (I_n- B)^{-1}\) se le llama la matriz fundamental para la cadena absorbente de Markov, donde In es una matriz de identidad del mismo tamaño que B. La\(i\),\(j\) -ésima entrada de esta matriz nos indica el número promedio de veces que el proceso está en el estado no absorbente\(j\) antes de la absorción si se comenzó en el estado no absorbente\(i\).

La matriz\(F = (I_n- B)^{-1}\) para nuestro problema se enumera a continuación.

Puedes usar tu calculadora, o una computadora, para calcular la matriz F.

La matriz Fundamental F nos ayuda a determinar el número promedio de juegos jugados antes de la absorción.

Según la matriz, la entrada 1.78 en la fila 3, columna 2 posición dice que la jugadora jugará el juego 1.78 veces antes de que pase de $3K a $2K. El ingreso 2.25 en la fila 3, columna 3 dice que si la jugadora ahora tiene $3K, tendrá $3K en promedio 2.25 veces antes de que termine el juego.

Ahora abordamos la cuestión de cuántas apuestas tendrá que hacer antes de ser absorbida, si el jugador comienza con $3K?

Si sumamos el número de juegos que juega el jugador en cada estado no absorbente, obtenemos el número promedio de juegos antes de la absorción de ese estado. Por lo tanto, si el jugador comienza con $3K, el promedio de juegos de Black Jack que jugará antes de la absorción es

\[1.07 + 1.78 + 2.25 + 0.90 = 6.0 \nonumber \]

Es decir, esperamos que el jugador tenga o bien 5.000 dólares o nada en la 7ª apuesta.

Por último, encontramos la matriz de soluciones sin elevar la matriz de transición a potencias superiores. La matriz FA nos da la matriz de solución.

\ [\ mathrm {FA} =\ left [\ begin {array} {cccc}
1.54 & .90 & .47 & .19\\
1.35 & 2.25 & 1.18 & .47\\
1.07 & 1.78 & 2.25 & .90\\
.64 & 1.07 & 1.35 & 1.54
\ end {array}\ right]\ left [\ begin {array} {cc}
.6 & 0\\
0 & 0\\
0 & 0\\
0 & .4
\ end {array}\ right] =\ left [\ begin {array} {cc}
.92 & .08\\
.81 & .19\\
.64 & .36\\
.38 & .62
\ end {array}\ derecha]\ nonumber\]

que es lo mismo que la siguiente matriz que obtuvimos elevando la matriz de transición a potencias superiores.

Ejemplo\(\PageIndex{6}\)

En una escuela profesional, los estudiantes necesitan tomar y aprobar una clase de escritura/discurso en inglés para obtener su título profesional. Los alumnos deberán tomar la clase durante el primer trimestre que se inscriban. Si no aprueban la clase la vuelven a tomar en el segundo semestre. Si fallan dos veces, no se les permite volver a tomarlo nuevamente, y así no podrían obtener su título.

Los alumnos pueden estar en uno de 4 estados: pasaron la clase (P), matriculados en la clase por primera vez (C), retomando la clase (R) o reprobaron dos veces y no pueden retomar (F). La experiencia muestra que 70% de los estudiantes que toman la clase por primera vez pasan y 80% de los estudiantes que toman la clase por segunda vez pasan.

Escribe la matriz de transición e identifica los estados absorbentes. Encontrar la probabilidad de ser absorbido eventualmente en cada uno de los estados absorbentes.

Solución

Los estados absorbentes son P (pase) y F (fallan repetidamente y no pueden retomar). La matriz de transición T se muestra a continuación.

Si elevamos la matriz de transición T a una potencia alta, encontramos que se mantiene estable y nos da las probabilidades a largo plazo de terminar en cada uno de los estados absorbentes.

De los estudiantes que actualmente toman la clase por primera vez, el 94% eventualmente aprobará. El 6% finalmente fallará dos veces y no podrá obtener su título.

De los estudiantes que actualmente toman la clase por segunda vez, el 80% eventualmente aprobará. El 20% finalmente fallará dos veces y no podrá obtener su título.

La matriz de solución contiene la misma información en forma abreviada

Tenga en cuenta que en este problema en particular, no necesitamos elevar T a una potencia “muy alta”. Si encontramos T ², vemos que en realidad es igual a T ⁿ para potencias superiores\(n\). T ⁿ se vuelve estable después de dos transiciones; esto tiene sentido en este problema porque después de tomar la clase dos veces, el alumno debe haber pasado o no se le permite volver a tomarla más. Por lo tanto, las probabilidades no deben cambiar más después de dos transiciones; al final de dos transiciones, cada estudiante ha alcanzado un estado absorbente.

Cadenas absorbentes de Markov

1. Una cadena de Markov es una cadena de Markov absorbente si tiene al menos un estado absorbente. Un estado i es un estado absorbente si una vez que el sistema alcanza el estado i, permanece en ese estado; es decir,\(p_{ii} = 1\).
2. Si una matriz de transición T para una cadena de Markov absorbente se eleva a potencias superiores, alcanza un estado absorbente llamado matriz de solución y permanece ahí. La\(i\),\(j\) -ésima entrada de esta matriz da la probabilidad de absorción en estado\(j\) mientras se inicia en estado\(i\).
3. Como alternativa, la matriz de solución se puede encontrar de la siguiente manera.
   1. Expresar la matriz de transición en la forma canónica de la siguiente manera. \ [\ mathrm {T} =\ left [\ begin {array} {ll}
      \ mathbf {I} _ {\ mathbf {n}} &\ mathbf {0}\
      \ mathbf {A} &\ mathbf {B}
      \ end {array}\ right]\ nonumber\] donde\(I_n\) es una matriz de identidad, y 0 es una matriz de todos los ceros.
   2. La matriz fundamental\(F = (I - B)^{-1}\). La matriz fundamental nos ayuda a encontrar el número de partidos jugados antes de la absorción.
   3. FA es la matriz de solución, cuya\(i\),\(j\) -ésima entrada da la probabilidad de absorción en estado\(j\) mientras se inicia en estado\(i\).
4. La suma de las entradas de una fila de la matriz fundamental nos da el número esperado de pasos antes de la absorción para el estado no absorbente asociado a esa fila.