En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , un proceso de llegada de Markoviano ( MAP o MArP [1] ) es un modelo matemático para el tiempo transcurrido entre las llegadas de trabajos a un sistema. El proceso más simple de este tipo es un proceso de Poisson donde el tiempo entre cada llegada se distribuye exponencialmente . [2] [3]
Los procesos fueron sugeridos por primera vez por Neuts en 1979. [2] [4]
Definición
Un proceso de llegada de Markov se define mediante dos matrices D 0 y D 1 donde los elementos de D 0 representan transiciones ocultas y los elementos de las transiciones observables D 1 . La matriz de bloques Q a continuación es una matriz de tasa de transición para una cadena de Markov de tiempo continuo . [5]
El ejemplo más simple es un proceso de Poisson donde D 0 = - λ y D 1 = λ donde solo hay una transición posible, es observable y ocurre a la tasa λ . Para que Q sea una matriz de tasas de transición válida, se aplican las siguientes restricciones a la D i
Casos especiales
Proceso de Poisson modulado por Markov
El proceso de Poisson modulado por Markov o MMPP donde m procesos de Poisson son conmutados por una cadena de Markov de tiempo continuo subyacente . [6] Si cada uno de los m procesos de Poisson tiene una tasa λ i y el Markov de tiempo continuo de modulación tiene una matriz R de tasa de transición m × m , entonces la representación de MAP es
Proceso de renovación de tipo de fase
El proceso de renovación de tipo fase es un proceso de llegada de Markov con estancia distribuida de tipo fase entre llegadas. Por ejemplo, si un proceso de llegada tiene una distribución de tiempo entre llegadas PH con un vector de salida denotado , el proceso de llegada tiene matriz generadora,
Proceso de llegada de lotes de Markov
El proceso de llegada por lotes de Markov ( BMAP ) es una generalización del proceso de llegada de Markov al permitir más de una llegada a la vez. [7] El caso homogéneo tiene una matriz de tasas,
Una llegada de tamaño ocurre cada vez que ocurre una transición en la submatriz . Submatrices tener elementos de , la tasa de un proceso de Poisson , tal que,
y
Adecuado
Se puede ajustar un MAP utilizando un algoritmo de maximización de expectativas . [8]
Software
- KPC-toolbox una biblioteca de scripts MATLAB para ajustar un MAP a los datos. [9]
Ver también
Referencias
- ^ Asmussen, SR (2003). "Modelos aditivos de Markov". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. 51 . págs. 302–339. doi : 10.1007 / 0-387-21525-5_11 . ISBN 978-0-387-00211-8.
- ^ a b Asmussen, S. (2000). "Modelos analíticos-matriciales y su análisis". Revista Escandinava de Estadística . 27 (2): 193–226. doi : 10.1111 / 1467-9469.00186 . JSTOR 4616600 .
- ^ Chakravarthy, SR (2011). "Procesos de llegada de Markov". Enciclopedia Wiley de Investigación de Operaciones y Ciencias de la Gestión . doi : 10.1002 / 9780470400531.eorms0499 . ISBN 9780470400531.
- ^ Neuts, Marcel F. (1979). "Un proceso versátil de puntos de Markov". Revista de probabilidad aplicada . Fideicomiso de probabilidad aplicada. 16 (4): 764–779. doi : 10.2307 / 3213143 . JSTOR 3213143 .
- ^ Casale, G. (2011). "Construcción de modelos de carga de trabajo precisos utilizando procesos de llegada de Markov". Revisión de la evaluación del desempeño de ACM SIGMETRICS . 39 : 357. doi : 10.1145 / 2007116.2007176 .
- ^ Fischer, W .; Meier-Hellstern, K. (1993). "El libro de cocina del proceso de Poisson modulado por Markov (MMPP)". Evaluación de desempeño . 18 (2): 149. doi : 10.1016 / 0166-5316 (93) 90035-S .
- ^ Lucantoni, DM (1993). "La cola BMAP / G / 1: un tutorial". Evaluación del desempeño de sistemas informáticos y de comunicación . Apuntes de conferencias en informática. 729 . págs. 330–358. doi : 10.1007 / BFb0013859 . ISBN 3-540-57297-X.
- ^ Buchholz, P. (2003). "Un algoritmo de EM para el ajuste de mapas a partir de datos de tráfico reales". Evaluación del rendimiento informático. Técnicas y herramientas de modelado . Apuntes de conferencias en informática. 2794 . págs. 218-236. doi : 10.1007 / 978-3-540-45232-4_14 . ISBN 978-3-540-40814-7.
- ^ Casale, G .; Zhang, EZ; Smirni, E. (2008). "Caja de herramientas de KPC: ajuste de seguimiento simple pero eficaz mediante procesos de llegada de Markov" (PDF) . 2008 Quinta Conferencia Internacional sobre Evaluación Cuantitativa de Sistemas . pag. 83. doi : 10.1109 / QEST.2008.33 . ISBN 978-0-7695-3360-5.