Aglomerabilidad

En teoría de probabilidad , la agrupabilidad es un método para reducir el tamaño del espacio de estados de algunas cadenas de Markov de tiempo continuo , publicado por primera vez por Kemeny y Snell. ^[1]

Definición

Supongamos que el espacio de estados completo de una cadena de Markov se divide en subconjuntos disjuntos de estados, donde estos subconjuntos se denotan por t _i . Esto forma una partición de los estados. Tanto el espacio de estados como la colección de subconjuntos pueden ser finitos o numerablemente infinitos. Una cadena de Markov de tiempo continuo es agrupable con respecto a la partición T si y solo si, para cualesquiera subconjuntos t _i y t _j en la partición, y para cualesquiera estados n,n' en el subconjunto t _i , ${\displaystyle \scriptstyle {T=\{t_{1},t_{2},\ldots \}}}$ ${\displaystyle \{X_{i}\}}$

${\displaystyle \sum _{m\in t_{j}}q(n,m)=\sum _{m\in t_{j}}q(n',m),}$

donde q ( i,j ) es la tasa de transición del estado i al estado j . ^[2]

De manera similar, para una matriz estocástica P , P es una matriz agrupable en una partición T si y solo si, para cualesquiera subconjuntos t _i y t _j en la partición, y para cualesquiera estados n,n' en el subconjunto t _i ,

${\displaystyle \sum _{m\in t_{j}}p(n,m)=\sum _{m\in t_{j}}p(n',m),}$

donde p ( i,j ) es la probabilidad de pasar del estado i al estado j . ^[3]

Ejemplo

Considere la matriz

${\displaystyle P={\begin{pmatrix}{\frac {1}{2}}&{\frac {3}{8}}&{\frac {1}{16}}&{\frac {1}{16}}\\{\frac {7}{16}}&{\frac {7}{16}}&0&{\frac {1}{8}}\\{\frac {1}{16}}&0&{\frac {1}{2}}&{\frac {7}{16}}\\0&{\frac {1}{16}}&{\frac {3}{8}}&{\frac {9}{16}}\end{pmatrix}}}$

y observe que se puede agrupar en la partición t  = {(1,2),(3,4)}, por lo que escribimos

${\displaystyle P_{t}={\begin{pmatrix}{\frac {7}{8}}&{\frac {1}{8}}\\{\frac {1}{16}}&{\frac {15}{16}}\end{pmatrix}}}$

y llamamos P _{t a} la matriz concentrada de P en t .

Procesos sucesivamente agrupables

En 2012, Katehakis y Smit descubrieron los procesos de agrupamiento sucesivo, para los cuales las probabilidades estacionarias se pueden obtener calculando sucesivamente las probabilidades estacionarias de una secuencia de cadenas de Markov construida de manera propicia. Cada una de estas últimas cadenas tiene un espacio de estados (normalmente mucho) más pequeño, lo que produce mejoras computacionales significativas. Estos resultados tienen muchas aplicaciones en modelos y problemas de confiabilidad y colas. ^[4]

Cuasi-aglomerabilidad

Franceschinis y Muntz introdujeron la cuasi-agrupabilidad, una propiedad por la cual un pequeño cambio en la matriz de velocidad hace que la cadena sea agrupable. ^[5]

Véase también

• Cadena de Markov casi completamente descomponible

Referencias

1. Kemeny, John G. ; Snell, J. Laurie (julio de 1976) [1960]. Gehring, FW; Halmos, PR (eds.). Cadenas finitas de Markov (segunda edición). Nueva York, Berlín, Heidelberg, Tokio: Springer-Verlag. p. 124. ISBN 978-0-387-90192-3.
2. Jane Hillston , Modelado markoviano compositivo utilizando un álgebra de procesos en las Actas del Segundo Taller Internacional sobre Solución Numérica de Cadenas de Markov: Cálculos con Cadenas de Markov, Raleigh, Carolina del Norte, enero de 1995. Kluwer Academic Press
3. Peter G. Harrison y Naresh M. Patel, Modelado del rendimiento de redes de comunicación y arquitecturas informáticas, Addison-Wesley, 1992
4. Katehakis, MN ; Smit, LC (2012). "Un procedimiento de agrupamiento sucesivo para una clase de cadenas de Markov". Probabilidad en la ingeniería y las ciencias de la información . 26 (4): 483. doi :10.1017/S0269964812000150.
5. Franceschinis, G.; Muntz, Richard R. (1993). "Límites para cadenas de Markov cuasi-agrupables". Evaluación del desempeño . 20 (1–3). Elsevier BV: 223–243. doi :10.1016/0166-5316(94)90015-9.