Hispanopedia Wiki
Articulo de referencia

Markovian arrival process

In queueing theory , a discipline within the mathematical theory of probability , a Markovian arrival process ( MAP or MArP [ 1 ] ) is a mathematical model for the time between ...

Hispanopedia WikiContenido en espanolLectura gratuita

In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process (MAP or MArP[1]) is a mathematical model for the time between job arrivals to a system. The simplest such process is a Poisson process where the time between each arrival is exponentially distributed.[2][3]

The processes were first suggested by Marcel F. Neuts in 1979.[2][4]

Definition

A Markov arrival process is defined by two matrices, D0 and D1 where elements of D0 represent hidden transitions and elements of D1 observable transitions. The block matrixQ below is a transition rate matrix for a continuous-time Markov chain.[5]

Q=[D0D100…0D0D10…00D0D1…⋮⋮⋱⋱⋱].{\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]\;.}

The simplest example is a Poisson process where D0 = −λ and D1 = λ where there is only one possible transition, it is observable, and occurs at rate λ. For Q to be a valid transition rate matrix, the following restrictions apply to the Di

0≤[D1]i,j<∞0≤[D0]i,j<∞i≠j[D0]i,i<0(D0+D1)1=0{\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}}}

Special cases

Phase-type renewal process

The phase-type renewal process is a Markov arrival process with phase-type distributed sojourn between arrivals. For example, if an arrival process has an interarrival time distribution PH(α,S){\displaystyle ({\boldsymbol {\alpha }},S)} with an exit vector denoted S0=−S1{\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}, the arrival process has generator matrix,

Q=[SS0α00…0SS0α0…00SS0α…⋮⋮⋱⋱⋱]{\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]}

Generalizations

Batch Markov arrival process

The batch Markovian arrival process (BMAP) is a generalisation of the Markovian arrival process by allowing more than one arrival at a time.[6][7] The homogeneous case has rate matrix,

Q=[D0D1D2D3…0D0D1D2…00D0D1…⋮⋮⋱⋱⋱].{\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]\;.}

An arrival of size k{\displaystyle k} occurs every time a transition occurs in the sub-matrix Dk{\displaystyle D_{k}}. Sub-matrices Dk{\displaystyle D_{k}} have elements of λi,j{\displaystyle \lambda _{i,j}}, the rate of a Poisson process, such that,

0≤[Dk]i,j<∞1≤k{\displaystyle 0\leq [D_{k}]_{i,j}<\infty \;\;\;\;1\leq k}
0≤[D0]i,j<∞i≠j{\displaystyle 0\leq [D_{0}]_{i,j}<\infty \;\;\;\;i\neq j}
[D0]i,i<0{\displaystyle [D_{0}]_{i,i}<0\;}

and

∑k=0∞Dk1=0{\displaystyle \sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}}

Markov-modulated Poisson process

El proceso de Poisson modulado por Markov o MMPP, donde m procesos de Poisson se conmutan mediante una cadena de Markov de tiempo continuo subyacente . [ 8 ] Si cada uno de los m procesos de Poisson tiene una tasa λ i y la cadena de Markov de tiempo continuo moduladora tiene una matriz de tasas de transición R de m  × m , entonces la representación MAP es 

D1=diagnóstico⁡{λ1,…,λmetro}D0=R−D1.{\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 expectativa-maximización . [ 9 ]

Software

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

Véase también

Referencias

  1. ↑ Asmussen, SR (2003). "Modelos aditivos de Markov". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol.  51. pp. 302–339 . doi : 10.1007/0-387-21525-5_11 . ISBN  978-0-387-00211-8.
  2. 1 2 Asmussen, S. (2000). " Modelos analíticos matriciales y su análisis" . Scandinavian Journal of Statistics . 27 (2): 193– 226. doi : 10.1111/1467-9469.00186 . JSTOR 4616600. S2CID 122810934 .  
  3. ↑ Chakravarthy, SR (2011). "Procesos de llegada markovianos". Wiley Encyclopedia of Operations Research and Management Science . doi : 10.1002/9780470400531.eorms0499 . ISBN 9780470400531.
  4. ↑ 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 .  
  5. ↑ Casale, G. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review . 39 : 357. doi : 10.1145/2007116.2007176 .
  6. ↑ Lucantoni, DM (1993). "La cola BMAP/G/1: Un tutorial". Evaluación del rendimiento de sistemas informáticos y de comunicación . Notas de clase en ciencias de la computación. Vol. 729. págs. 330–358 . doi : 10.1007/BFb0013859 . ISBN   3-540-57297-X. S2CID 35110866 . 
  7. ↑ Singh, Gagandeep; Gupta, UC; Chaudhry, ML (2016). "Análisis computacional detallado de las distribuciones del tiempo de espera en la cola BMAP/G/1 utilizando raíces" . Journal of Applied Probability . 53 (4): 1078– 1097. doi : 10.1017/jpr.2016.66 . S2CID 27505255 . 
  8. ↑ Fischer, W.; Meier-Hellstern, K. (1993). "El libro de recetas del proceso de Poisson modulado por Markov (MMPP)". Performance Evaluation . 18 (2): 149. doi : 10.1016/0166-5316(93)90035-S .
  9. ↑ Buchholz, P. (2003). "Un algoritmo EM para el ajuste de mapas de tráfico a partir de datos de tráfico reales". Evaluación del rendimiento informático. Técnicas y herramientas de modelado . Notas de clase en ciencias de la computación. 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 efectivo mediante procesos de llegada markovianos" (PDF) . Quinta Conferencia Internacional de 2008 sobre Evaluación Cuantitativa de Sistemas . pág. 83. doi : 10.1109/QEST.2008.33 . ISBN  978-0-7695-3360-5. S2CID 252444 .