Cadena de Markov absorbente

Cadena de Markov en la que todos los estados pueden ser absorbentes

El paseo de un borracho (finito) es un ejemplo de una cadena de Markov absorbente. ^[1]

En la teoría matemática de la probabilidad , una cadena de Markov absorbente es una cadena de Markov en la que cada estado puede alcanzar un estado absorbente. Un estado absorbente es un estado del que, una vez ingresado, no se puede salir.

Al igual que las cadenas de Markov generales, puede haber cadenas de Markov absorbentes en tiempo continuo con un espacio de estados infinito. Sin embargo, este artículo se concentra en el caso de espacio de estados discreto en tiempo discreto.

Definición formal

Una cadena de Markov es una cadena absorbente si ^{[1] [2]}

1. Hay al menos un estado absorbente y
2. Es posible pasar de cualquier estado a al menos un estado absorbente en un número finito de pasos.

En una cadena de Markov absorbente, un estado que no es absorbente se denomina transitorio.

Forma canónica

Sea una cadena absorbente de Markov con matriz de transición P que tenga t estados transitorios y r estados absorbentes. A diferencia de una matriz de transición típica, las filas de P representan fuentes, mientras que las columnas representan destinos. Entonces

${\displaystyle P={\begin{bmatrix}Q&R\\\mathbf {0} &I_{r}\end{bmatrix}},}$

donde Q es una matriz t por t , R es una matriz t por r distinta de cero, 0 es una matriz cero r por t e I _r es la matriz identidad r por r . Por lo tanto, Q describe la probabilidad de transición de un estado transitorio a otro, mientras que R describe la probabilidad de transición de un estado transitorio a un estado absorbente.

La probabilidad de transición de i a j en exactamente k pasos es la entrada ( i , j ) de P ^k , calculada con más detalle a continuación. Al considerar solo los estados transitorios, la probabilidad que se encuentra en la parte superior izquierda de P ^k , la entrada ( i , j ) de Q ^k .

Matriz fundamental

Número esperado de visitas a un estado transitorio

Una propiedad básica de una cadena de Markov absorbente es el número esperado de visitas a un estado transitorio j a partir de un estado transitorio i (antes de ser absorbida). Se puede establecer que esto viene dado por la entrada ( i ,  j ) de la llamada matriz fundamental N , obtenida sumando Q ^k para todos los k (de 0 a ∞). Se puede demostrar que

${\displaystyle N:=\sum _{k=0}^{\infty }Q^{k}=(I_{t}-Q)^{-1},}$

donde I _t es la matriz identidad t por t . El cálculo de esta fórmula es la matriz equivalente de la serie geométrica de escalares, . ${\displaystyle {\textstyle \sum }_{k=0}^{\infty }q^{k}={\tfrac {1}{1-q}}}$

Con la matriz N en mano, también es fácil obtener otras propiedades de la cadena de Markov. ^[2]

Número esperado de pasos antes de ser absorbido

El número esperado de pasos antes de ser absorbido en cualquier estado absorbente, al comenzar en el estado transitorio i, se puede calcular mediante una suma de los estados transitorios. El valor se da por la entrada i del vector

${\displaystyle \mathbf {t} :=N\mathbf {1} ,}$

donde 1 es un vector de columna de longitud t cuyas entradas son todas 1.

Absorbiendo probabilidades

Por inducción,

${\displaystyle P^{k}={\begin{bmatrix}Q^{k}&(1-Q^{k})NR\\\mathbf {0} &I_{r}\end{bmatrix}}.}$

La probabilidad de ser finalmente absorbido en el estado absorbente j al partir del estado transitorio i está dada por la entrada ( i , j ) de la matriz

${\displaystyle B:=NR}$.

El número de columnas de esta matriz es igual al número de estados absorbentes r .

También se puede obtener una aproximación de esas probabilidades directamente a partir de la entrada ( i , j ) de para un valor suficientemente grande de k , cuando i es el índice de un estado transitorio y j el índice de un estado absorbente. Esto se debe a que ${\displaystyle P^{k}}$

${\displaystyle \left(\lim _{k\to \infty }P^{k}\right)_{i,t+j}=B_{i,j}}$.

Probabilidades de visitas transitorias

La probabilidad de visitar el estado transitorio j al comenzar en un estado transitorio i es la entrada ( i , j ) de la matriz

${\displaystyle H:=(N-I_{t})(N_{\operatorname {dg} })^{-1},}$

donde N _dg es la matriz diagonal con la misma diagonal que N .

Variación en el número de visitas transitorias

La varianza en el número de visitas a un estado transitorio j comenzando en un estado transitorio i (antes de ser absorbido) es la entrada ( i , j ) de la matriz

${\displaystyle N_{2}:=N(2N_{\operatorname {dg} }-I_{t})-N_{\operatorname {sq} },}$

donde N _sq es el producto Hadamard de N consigo mismo (es decir, cada entrada de N se eleva al cuadrado).

Variación en el número de pasos

La varianza en el número de pasos antes de ser absorbido al comenzar en el estado transitorio i es la i- ésima entrada del vector

${\displaystyle (2N-I_{t})\mathbf {t} -\mathbf {t} _{\operatorname {sq} },}$

donde t _sq es el producto de Hadamard de t consigo mismo (es decir, como con N _sq , cada entrada de t se eleva al cuadrado).

Ejemplos

Generación de cadenas

Considere el proceso de lanzar repetidamente una moneda justa hasta que aparezca la secuencia (cara, cruz, cara). Este proceso se modela mediante una cadena de Markov absorbente con matriz de transición.

${\displaystyle P={\begin{bmatrix}1/2&1/2&0&0\\0&1/2&1/2&0\\1/2&0&0&1/2\\0&0&0&1\end{bmatrix}}.}$

Una cadena de Markov con 4 estados para el problema de generación de cuerdas.

El primer estado representa la cadena vacía , el segundo estado la cadena "H", el tercer estado la cadena "HT" y el cuarto estado la cadena "HTH". Aunque en realidad los lanzamientos de moneda cesan después de que se genera la cadena "HTH", la perspectiva de la cadena de Markov absorbente es que el proceso ha pasado al estado absorbente que representa la cadena "HTH" y, por lo tanto, no puede salir.

Para esta cadena absorbente de Markov, la matriz fundamental es

${\displaystyle {\begin{aligned}N&=(I-Q)^{-1}=\left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}-{\begin{bmatrix}1/2&1/2&0\\0&1/2&1/2\\1/2&0&0\end{bmatrix}}\right)^{-1}\\[4pt]&={\begin{bmatrix}1/2&-1/2&0\\0&1/2&-1/2\\-1/2&0&1\end{bmatrix}}^{-1}={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}.\end{aligned}}}$

El número esperado de pasos a partir de cada uno de los estados transitorios es

${\displaystyle \mathbf {t} =N\mathbf {1} ={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}10\\8\\6\end{bmatrix}}.}$

Por lo tanto, el número esperado de lanzamientos de moneda antes de observar la secuencia (cara, cruz, cara) es 10, la entrada para el estado que representa la cadena vacía.

La probabilidad acumulada de terminar un juego de Serpientes y Escaleras en el turno  N

Juegos de azar

Los juegos basados ​​completamente en el azar pueden modelarse mediante una cadena absorbente de Markov. Un ejemplo clásico de esto es el antiguo juego de mesa indio Serpientes y escaleras . El gráfico de la izquierda ^[3] representa la masa de probabilidad en el único estado absorbente que representa el cuadrado final a medida que la matriz de transición se eleva a potencias cada vez mayores. Para determinar el número esperado de turnos para completar el juego, calcule el vector t como se describió anteriormente y examine t _start , que es aproximadamente 39,2.

Pruebas de enfermedades infecciosas

Las pruebas de enfermedades infecciosas, ya sea de productos sanguíneos o en clínicas médicas, a menudo se enseñan como un ejemplo de una cadena de Markov absorbente. ^[4] El modelo público de los Centros para el Control y la Prevención de Enfermedades (CDC) de los EE. UU. para el VIH y la hepatitis B, por ejemplo, ^[5] ilustra la propiedad de que la absorción de cadenas de Markov puede conducir a la detección de enfermedades, frente a la pérdida de detección a través de otros medios.

En el modelo estándar de los CDC, la cadena de Markov tiene cinco estados: un estado en el que el individuo no está infectado, luego un estado con el virus infectado pero indetectable, un estado con el virus detectable y estados absorbentes de haber abandonado/haberse perdido de la clínica, o de haber sido detectado (el objetivo). Las tasas típicas de transición entre los estados de Markov son la probabilidad p por unidad de tiempo de estar infectado con el virus, w para la tasa de eliminación del período ventana (tiempo hasta que el virus es detectable), q para la tasa de abandono/pérdida del sistema, y ​​d para la detección, suponiendo una tasa típica a la que el sistema de salud administra pruebas del producto sanguíneo o de los pacientes en cuestión. ${\displaystyle \lambda }$

Ejemplo clásico de modelo de detección del virus del VIH o de la hepatitis

De ello se deduce que podemos "recorrer" el modelo de Markov para identificar la probabilidad general de detección de una persona que comienza sin ser detectada, multiplicando las probabilidades de transición a cada siguiente estado del modelo como:

${\displaystyle {\frac {p}{(p+q)}}{\frac {w}{(w+q)}}{\frac {d}{(d+q)}}}$.

El número absoluto total subsiguiente de pruebas de falsos negativos (la principal preocupación de los CDC) sería entonces la tasa de pruebas, multiplicada por la probabilidad de alcanzar el estado infectado pero indetectable, multiplicada por la duración de la permanencia en el estado infectado pero indetectable:

${\displaystyle {\frac {p}{(p+q)}}{\frac {1}{(w+q)}}\lambda }$.

Véase también

• Distribución de tipo fase discreta
• Conjunto absorbente (sistemas dinámicos aleatorios)

Referencias

1. Grinstead, Charles M.; Snell, J. Laurie (julio de 1997). "Cap. 11: Cadenas de Markov" (PDF) . Introducción a la probabilidad . Sociedad Matemática Estadounidense. ISBN 978-0-8218-0749-1.
2. Kemeny, John G. ; Snell, J. Laurie (julio de 1976) [1960]. "Cap. 3: Cadenas de Markov absorbentes". En Gehring, FW; Halmos, PR (eds.). Cadenas de Markov finitas (segunda edición). Nueva York, Berlín, Heidelberg, Tokio: Springer-Verlag. págs. 224. ISBN 978-0-387-90192-3.
3. Basado en la definición encontrada en SC Althoen; L. King; K. Schilling (marzo de 1993). "How Long Is a Game of Snakes and Ladders?". The Mathematical Gazette . 78 (478). The Mathematical Gazette, vol. 77, núm. 478: 71–76. doi :10.2307/3619261. JSTOR  3619261.
4. Resultados de búsqueda (28 de julio de 1998). Cadenas de Markov. Cambridge: Cambridge University Press. ISBN 9780521633963.
5. Sanders, Gillian D.; Anaya, Henry D.; Asch, Steven; Hoang, Tuyen; Golden, Joya F.; Bayoumi, Ahmed M.; Owens, Douglas K. (junio de 2010). "Relación coste-eficacia de las estrategias para mejorar las pruebas de VIH y la recepción de los resultados: análisis económico de un ensayo controlado aleatorio". Revista de Medicina Interna General . 25 (6): 556–563. doi :10.1007/s11606-010-1265-5. ISSN  0884-8734. PMC 2869414 . PMID  20204538. 

Enlaces externos

• Proyecto de demostración de Wolfram: absorción de la cadena de Markov
• El monopolio como cadena de Markov