Hispanopedia Wiki
Articulo de referencia

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 markoviano ( MAP o MArP [ 1 ] ) es un modelo matemático para el ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 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 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 de D₁ , transiciones observables. La matriz de bloques Q que se muestra a continuación es una matriz de tasas de transición para una cadena de Markov de tiempo continuo . [ 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]\;.}

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 una tasa λ . Para que Q sea una matriz de tasas de transición válida, se aplican las siguientes restricciones a D i 

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}}}

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 permanencia distribuida de tipo fase entre llegadas. Por ejemplo, si un proceso de llegada tiene una distribución de tiempo entre llegadas PH(α,S){\displaystyle ({\boldsymbol {\alpha }},S)}con un vector de salida denotadoS0=−S1{\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}, el proceso de llegada tiene matriz generadora,

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]}

Generalizaciones

Proceso de llegada de Markov por lotes

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 matriz de tasas,

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]\;.}

Una llegada de tamañok{\displaystyle k}ocurre cada vez que se produce una transición en la submatriz.Dk{\displaystyle D_{k}}SubmatricesDk{\displaystyle D_{k}}tienen elementos deλi,j{\displaystyle \lambda _{i,j}}, la tasa de un proceso de Poisson , tal que,

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\;}

y

∑k=0∞Dk1=0{\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 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 .