# Procés d'arribada markovià

En la teoria de cues, una disciplina dins de la teoria matemàtica de la probabilitat, un procés d'arribada markovià (en anglès, Markovian arrival process, MAP o MArP) és un model matemàtic per al temps entre les arribades de treball a un sistema. El procés més senzill és un procés de Poisson, on el temps entre cada arribada es distribueix exponencialment.
Els processos van ser suggerits per Neuts el 1979.

## Definició

Un procés d'arribada de Màrkov està definit per dues matrius, D$_0$ i D$_1$, on els elements de D$_0$ representen transicions ocultes i els elements D$_1$ les transicions observables. La matriu per blocs Q següent és una matriu de velocitat de transferència per a una cadena de Màrkov a temps continu.
    $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]\;.$
L'exemple més senzill és un procés de Poisson (on D$_0$ = −λ i D$_1$ = λ), on només hi ha una possible transició, és observable i es produeix al ritme λ. Perquè Q sigui una matriu de velocitat de transferència vàlida, les restriccions següents s'apliquen 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 especials
### Procés de Poisson modulat per Màrkov

En el procés de Poisson modulat per Màrkov (en anglès, Markov-Modulated Poisson Process, MMPP), els m processos de Poisson són canviats per una cadena de Màrkov subjacent de temps continu. Si cadascun dels m processos de Poisson tenen una velocitat λ$_i$ i el temps continu modulat per Màrkov té una matriu m × m de velocitat de transferència R, llavors la representació del MAP és
    ${\begin{aligned}D_{1}&=\operatorname {diag} \{\lambda _{1},\dots ,\lambda _{m}\}\\D_{0}&=R-D_{1}.\end{aligned}}$

### Procés de renovació de tipus fase

El procés de renovació del tipus de fase és un procés d'arribada mMàrkovià amb un trajecte distribuït de tipus fase entre arribades. Per exemple, si un procés d'arribada té una distribució de temps entre arrivades PH$({\boldsymbol {\alpha }},S)$ amb un vector de sortida denotat ${\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}$, el procés d'arribada té matriu generatriu,
    $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]$

## Procés d'arribada per lots de Markov

Un procés d'arribada per lots de Markov (en anglès, Batch Markovian Arrival Process, BMAP) és una generalització del procés d'arribada markovià que permet més d'una arribada a la vegada. El cas homogeni té com a matriu de velocitat,
    $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 arribada de mida $k$ es produeix cada vegada que es produeix una transició a la submatriu $D_{k}$. Les submatrius $D_{k}$ tenen elements de $\lambda _{i,j}$, la velocitat d'un procés de Poisson, de manera que,
    $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\;$
i
    $\sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}$

## Encaix

Un procés d'arribada markovià es pot encaixar utilitzant un algorisme d'esperança-maximització.

### Programari

* KPC-toolbox, una biblioteca de scripts MATLAB per adaptar-se a un mapa de dades.

## Referències

* ↑ Asmussen, S. R. «Markov Additive Models». A: Applied Probability and Queues (en anglès). 51, 2003, p. 302–339 (Stochastic Modelling and Applied Probability). DOI 10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.
* 1 2 Asmussen, S «Matrix-analytic Models and their Analysis» (en anglès). Scandinavian Journal of Statistics, 27(2), 2000, pàg. 193–226. DOI: 10.1111/1467-9469.00186. JSTOR: 4616600.
* ↑ Chakravarthy, S. R. «Markovian Arrival Processes». A: Wiley Encyclopedia of Operations Research and Management Science (en anglès), 2011. DOI 10.1002/9780470400531.eorms0499. ISBN 9780470400531.
* ↑ Neuts, Marcel F «A Versatile Markovian Point Process» (en anglès). Journal of Applied Probability, 16(4), 1979, pàg. 764–779. DOI: 10.2307/3213143. JSTOR: 3213143.
* ↑ Casale, G «Building accurate workload models using Markovian arrival processes» (en anglès). ACM SIGMETRICS Performance Evaluation Review, 39, 2011, pàg. 357. DOI: 10.1145/2007116.2007176.
* ↑ Fischer, W; Meier-Hellstern, K «The Markov-modulated Poisson process (MMPP) cookbook» (en anglès). Performance Evaluation, 18(2), 1993, pàg. 149. DOI: 10.1016/0166-5316(93)90035-S.
* ↑ Lucantoni, D. M. «The BMAP/G/1 queue: A tutorial». A: Performance Evaluation of Computer and Communication Systems (en anglès). 729, 1993, p. 330–358 (Lecture Notes in Computer Science). DOI 10.1007/BFb0013859. ISBN 3-540-57297-X.
* ↑ Buchholz, P. «An EM-Algorithm for MAP Fitting from Real Traffic Data». A: Computer Performance Evaluation. Modelling Techniques and Tools (en anglès). 2794, 2003, p. 218–236 (Lecture Notes in Computer Science). DOI 10.1007/978-3-540-45232-4_14. ISBN 978-3-540-40814-7.
* ↑ Casale, G; Zhang, E. Z; Smirni, E. «KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes». A: 2008 Fifth International Conference on Quantitative Evaluation of Systems ( PDF) (en anglès), 2008, p. 83. DOI 10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5.