Proceso de llegada markoviano

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , un proceso de llegada de Markov ( MAP o MArP ^[1] ) es un modelo matemático para el tiempo entre llegadas de trabajos a un sistema. El proceso más simple 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 está definido por dos matrices, D ₀ y D _1, donde los elementos de D ₀ representan transiciones ocultas y los elementos de D ₁ transiciones observables. La matriz de bloques Q siguiente es una matriz de tasa de transición para una cadena de Markov de tiempo continuo . ^[5]

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&0&0&\dots \\0&D_{0}&D_{1}&0&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\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 velocidad λ . Para que Q sea una matriz de tasa de transición válida, se aplican las siguientes restricciones a D _i

${\displaystyle {\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 tipo 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 denominado , el proceso de llegada tiene una matriz generadora, ${\displaystyle ({\boldsymbol {\alpha }},S)}$ ${\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}$

${\displaystyle Q=\left[{\begin{matrix}S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&0&\dots \\0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&\dots \\0&0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \\\end{matrix}}\right]}$

Generalizaciones

Proceso de llegada de lotes de Markov

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

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&D_{2}&D_{3}&\dots \\0&D_{0}&D_{1}&D_{2}&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \end{matrix}}\right]\;.}$

Una llegada de tamaño ocurre cada vez que ocurre una transición en la submatriz . Las submatrices tienen elementos de la tasa de un proceso de Poisson , tales que, ${\displaystyle k}$ ${\displaystyle D_{k}}$ ${\displaystyle D_{k}}$ ${\displaystyle \lambda _{i,j}}$

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

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

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

y

${\displaystyle \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 conmutan entre sí mediante una cadena de Markov subyacente de tiempo continuo . ^[8] Si cada uno de los m procesos de Poisson tiene una velocidad λ _i y la modulación de tiempo continuo de Markov tiene una matriz de velocidad de transición m  ×  m R , entonces la representación MAP es

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

Adecuado

Se puede ajustar un MAP utilizando un algoritmo de maximización de expectativas . ^[9]

Software

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

Ver también

• Proceso de llegada racional

Referencias

1. Asmussen, SR (2003). "Modelos aditivos de Markov". Probabilidad Aplicada y Colas . Modelización estocástica y probabilidad aplicada. vol. 51, págs. 302–339. doi :10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.
2. 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.
3. Chakravarthy, SR (2011). "Procesos de llegada markovianos". Enciclopedia Wiley de investigación de operaciones y ciencias de la gestión . doi : 10.1002/9780470400531.eorms0499. ISBN 9780470400531.
4. Neuts, Marcel F. (1979). "Un proceso de puntos markoviano versátil". Revista de probabilidad aplicada . 16 (4). Fideicomiso de probabilidad aplicada: 764–779. doi :10.2307/3213143. JSTOR  3213143. S2CID  123525892.
5. Casale, G. (2011). "Construcción de modelos precisos de carga de trabajo utilizando procesos de llegada de Markov". Revisión de evaluación del desempeño de ACM SIGMETRICS . 39 : 357. doi : 10.1145/2007116.2007176.
6. Lucantoni, DM (1993). "La cola BMAP/G/1: un tutorial". Evaluación del Desempeño de Sistemas Informáticos y de Comunicaciones . Apuntes de conferencias sobre informática. vol. 729, págs. 330–358. doi :10.1007/BFb0013859. ISBN 3-540-57297-X. S2CID  35110866.
7. Singh, Gagandeep; Gupta, Universidad de California; Chaudhry, ML (2016). "Análisis computacional detallado de las distribuciones de tiempo de cola de la cola BMAP/G/1 utilizando raíces". Revista de probabilidad aplicada . 53 (4): 1078–1097. doi : 10.1017/jpr.2016.66. S2CID  27505255.
8. Fischer, W.; Meier-Hellstern, K. (1993). "El libro de cocina del proceso de Poisson modulado por Markov (MMPP)". Evaluación del desempeño . 18 (2): 149. doi :10.1016/0166-5316(93)90035-S.
9. 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 conferencias sobre informática. vol. 2794, págs. 218–236. doi :10.1007/978-3-540-45232-4_14. ISBN 978-3-540-40814-7.
10. Casale, G.; Zhang, EZ; Smirni, E. (2008). "KPC-Toolbox: Ajuste de trazas 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. S2CID  252444.