Proceso de llegada de Markovian

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , un proceso de llegada markoviano ( MAP o MArP ^[1] ) es un modelo matemático para el tiempo entre la llegada 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 Marcel F. Neuts en 1979. ^[2]^[4]

Definición

Un proceso de llegada de Markov se define mediante dos matrices, D ₀ y D ₁ , donde los elementos de D ₀ representan transiciones ocultas y los elementos de D ₁ transiciones observables. La matriz de bloques Q que aparece a continuación es una matriz de tasa de transición para una cadena de Markov de tiempo continuo . ^[5]

Q=\left[{\begin{matrix}D_{0}&D_{1}&0&0&\puntos \\0&D_{0}&D_{1}&0&\puntos \\0&0&D_{0}&D_{1}&\puntos \\\vpuntos &\vpuntos &\dpuntos &\dpuntos &\ddots \end{matrix}}\right]\;.

El ejemplo más simple es un proceso de Poisson donde D ₀ = − λ y D ₁ = λ donde solo hay una transición posible, es observable y ocurre a una tasa λ . Para que Q sea una matriz de tasa de transición válida, se aplican las siguientes restricciones a D _i

{\begin{aligned}0\leq [D_{1}]_{i,j}&<\infty \\0\leq [D_{0}]_{i,j}&<\infty \quad i\neq j\\\,[D_{0}]_{i,i}&<0\\(D_{0}+D_{1}){\boldsymbol {1}}&={\boldsymbol {0}}\end{aligned}}

Casos especiales

Proceso de renovación por fases

El proceso de renovación de tipo fase es un proceso de llegada de Markov con una 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 como , el proceso de llegada tiene una matriz generadora, $({\boldsymbol {\alpha }},S)$ ${\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}$

Q=\left[{\begin{matriz}S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&0&\puntos \\0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&\puntos \\0&0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&\puntos \\\vpuntos &\vpuntos &\dpuntos &\dpuntos &\dpuntos \\\end{matriz}}\right]

Generalizaciones

Proceso de llegada de lotes de Markov

El proceso de llegada markoviano por lotes ( BMAP ) es una generalización del proceso de llegada markoviano al permitir más de una llegada a la vez. ^[6] ^[7] El caso homogéneo tiene una matriz de velocidad,

Q=\left[{\begin{matrix}D_{0}&D_{1}&D_{2}&D_{3}&\puntos \\0&D_{0}&D_{1}&D_{2}&\puntos \\0&0&D_{0}&D_{1}&\puntos \\\vpuntos &\vpuntos &\dpuntos &\dpuntos &\ddots \end{matrix}}\right]\;.

Se produce una llegada de tamaño cada vez que se produce una transición en la submatriz . Las submatrices tienen elementos de , la tasa de un proceso de Poisson , de modo que, ${\estilo de visualización k}$ $D_{k}$ $D_{k}$ $\lambda _ {i,j}$

0\leq [D_{k}]_{i,j}<\infty \;\;\;\;1\leq k

0\leq [D_{0}]_{i,j}<\infty \;\;\;\;i\neq j

[D_{0}]_{i,i}<0\;

\sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}

Proceso de Poisson modulado por Markov

El proceso de Poisson modulado por Markov o MMPP , donde m procesos de Poisson se alternan entre sí mediante una cadena de Markov de tiempo continuo subyacente . ^[8] Si cada uno de los m procesos de Poisson tiene una tasa λ _i y el proceso de Markov modulador de tiempo continuo tiene una matriz de tasa de transición m × m R , entonces la representación MAP es

{\begin{aligned}D_{1}&=\operatorname {diag} \{\lambda _{1},\dots ,\lambda _{m}\}\\D_{0}&=R-D_{1}.\end{aligned}}

Adecuado

Un MAP se puede ajustar utilizando un algoritmo de expectativa-maximización . ^[9]

Software

KPC-toolbox es una biblioteca de scripts de MATLAB para adaptar un MAP a los datos. ^[10]

Véase también

Proceso de llegada racional

Referencias

^ Asmussen, SR (2003). "Markov Additive Models". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol. 51. págs. 302–339. doi :10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.
^ ab 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. S2CID 122810934.
^ Chakravarthy, SR (2011). "Procesos de llegada markovianos". Enciclopedia Wiley de investigación de operaciones y ciencia de la gestión . doi :10.1002/9780470400531.eorms0499. ISBN 9780470400531.
^ Neuts, Marcel F. (1979). "Un proceso puntual markoviano versátil". Journal of Applied Probability . 16 (4). Applied Probability Trust: 764–779. doi :10.2307/3213143. JSTOR 3213143. S2CID 123525892.
^ Casale, G. (2011). "Construcción de modelos de carga de trabajo precisos utilizando procesos de llegada markovianos". Revisión de evaluación del rendimiento de ACM SIGMETRICS . 39 : 357. doi :10.1145/2007116.2007176.
^ Lucantoni, DM (1993). "La cola BMAP/G/1: un tutorial". Evaluación del rendimiento de sistemas informáticos y de comunicación . Apuntes de clase en informática. Vol. 729. págs. 330–358. doi :10.1007/BFb0013859. ISBN 3-540-57297-X. Número de identificación del sujeto 35110866.
^ Singh, Gagandeep; Gupta, UC; Chaudhry, ML (2016). "Análisis computacional detallado de distribuciones de tiempo de espera de la cola BMAP/G/1 usando raíces". Journal of Applied Probability . 53 (4): 1078–1097. doi :10.1017/jpr.2016.66. S2CID 27505255.
^ Fischer, W.; Meier-Hellstern, K. (1993). "El libro de recetas del proceso de Poisson modulado por Markov (MMPP)". Evaluación del rendimiento . 18 (2): 149. doi :10.1016/0166-5316(93)90035-S.
^ Buchholz, P. (2003). "Un algoritmo EM para el ajuste de MAP a partir de datos de tráfico reales". Evaluación del rendimiento informático. Técnicas y herramientas de modelado . Apuntes de clase en informática. Vol. 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). "KPC-Toolbox: Ajuste de trazas simple pero efectivo utilizando procesos de llegada markovianos" (PDF) . 2008 Quinta Conferencia Internacional sobre Evaluación Cuantitativa de Sistemas . p. 83. doi :10.1109/QEST.2008.33. ISBN. 978-0-7695-3360-5.S2CID252444 .