En la teoría de la probabilidad , el método analítico matricial es una técnica para calcular la distribución de probabilidad estacionaria de una cadena de Markov que tiene una estructura repetitiva (después de algún punto) y un espacio de estados que crece ilimitadamente en no más de una dimensión. [1] [2] Estos modelos a menudo se describen como cadenas de Markov de tipo M / G / 1 porque pueden describir transiciones en una cola M / G / 1. [3] [4] El método es una versión más complicada del método geométrico matricial y es el método de solución clásico para cadenas M / G / 1. [5]
Descripción del método
Una matriz estocástica de tipo M / G / 1 es una de las formas [3]
donde B i y A i son k × k matrices. (Tenga en cuenta que las entradas de la matriz sin marcar representan ceros). Tal matriz describe la cadena de Markov incrustada en una cola M / G / 1. [6] [7] Si P es irreducible y recurrente positivo, entonces la distribución estacionaria viene dada por la solución de las ecuaciones [3]
donde e representa un vector de dimensión adecuada con todos los valores iguales a 1. Al coincidir con la estructura de P , π se divide en π 1 , π 2 , π 3 ,…. Para calcular estas probabilidades, la matriz estocástica de columnas G se calcula de manera que [3]
G se llama matriz auxiliar. [8] Se definen matrices [3]
entonces π 0 se encuentra resolviendo [3]
y los π i están dados por la fórmula de Ramaswami , [3] una relación numéricamente estable publicada por primera vez por Vaidyanathan Ramaswami en 1988. [9]
Cálculo de G
Hay dos métodos iterativos populares para calcular G , [10] [11]
- iteraciones funcionales
- reducción cíclica .
Herramientas
Referencias
- ^ Harchol-Balter, M. (2012). "Distribuciones de tipo de fase y métodos analíticos de matriz". Modelado y Diseño de Performance de Sistemas Computacionales . págs. 359–379. doi : 10.1017 / CBO9781139226424.028 . ISBN 9781139226424.
- ^ Neuts, MF (1984). "Métodos analíticos-matriciales en la teoría de colas". Revista europea de investigación operativa . 15 : 2-12. doi : 10.1016 / 0377-2217 (84) 90034-1 .
- ^ a b c d e f g Meini, B. (1997). "Una versión mejorada basada en FFT de la fórmula de Ramaswami". Comunicaciones en estadística. Modelos estocásticos . 13 (2): 223–238. doi : 10.1080 / 15326349708807423 .
- ^ Stathopoulos, A .; Riska, A .; Hua, Z .; Smirni, E. (2005). "Bridging ETAQA y la fórmula de Ramaswami para la solución de procesos tipo M / G / 1". Evaluación de desempeño . 62 (1–4): 331–348. CiteSeerX 10.1.1.80.9473 . doi : 10.1016 / j.peva.2005.07.003 .
- ^ Riska, A .; Smirni, E. (2002). "Procesos de Markov tipo M / G / 1: un tutorial" (PDF) . Evaluación del desempeño de sistemas complejos: técnicas y herramientas . Apuntes de conferencias en Ciencias de la Computación. 2459 . págs. 36 . doi : 10.1007 / 3-540-45798-4_3 . ISBN 978-3-540-44252-3.
- ^ Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Redes de colas y cadenas de Markov: modelado y evaluación del rendimiento con aplicaciones informáticas (2 ed.). John Wiley & Sons, Inc. pág. 250. ISBN 978-0471565253.
- ^ Artalejo, Jesús R .; Gómez-Corral, Antonio (2008). "El formalismo analítico-matricial". Sistemas de cola de reelaboración . págs. 187-205. doi : 10.1007 / 978-3-540-78725-9_7 . ISBN 978-3-540-78724-2.
- ^ Riska, A .; Smirni, E. (2002). "Soluciones de áridos exactos para procesos de Markov tipo M / G / 1". Revisión de la evaluación del desempeño de ACM SIGMETRICS . 30 : 86. CiteSeerX 10.1.1.109.2225 . doi : 10.1145 / 511399.511346 .
- ^ Ramaswami, V. (1988). "Una recursividad estable para el vector de estado estacionario en cadenas de Markov de tipo m / g / 1". Comunicaciones en estadística. Modelos estocásticos . 4 : 183–188. doi : 10.1080 / 15326348808807077 .
- ^ Bini, DA; Latouche, G .; Meini, B. (2005). Métodos numéricos para cadenas de Markov estructuradas . doi : 10.1093 / acprof: oso / 9780198527688.001.0001 . ISBN 9780198527688.
- ^ Meini, B. (1998). "Resolución de cadenas de markov tipo m / g / l: avances y aplicaciones recientes". Comunicaciones en estadística. Modelos estocásticos . 14 (1–2): 479–496. doi : 10.1080 / 15326349808807483 .
- ^ Riska, A .; Smirni, E. (2002). "MAMSolver: una herramienta de métodos analíticos de matriz". Evaluación del rendimiento informático: técnicas y herramientas de modelado . Apuntes de conferencias en Ciencias de la Computación. 2324 . pag. 205. CiteSeerX 10.1.1.146.2080 . doi : 10.1007 / 3-540-46029-2_14 . ISBN 978-3-540-43539-6.