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)^[1] é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.^[2][3]

Els processos van ser suggerits per Neuts el 1979.^[2][4]

Definició

Un procés d'arribada de Màrkov està definit per dues matrius, D₀ i D₁, on els elements de D₀ representen transicions ocultes i els elements D₁ 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.^[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]\;.}$

L'exemple més senzill és un procés de Poisson (on D₀ = −λ i D₁ = λ), 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

${\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 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.^[6] 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

${\displaystyle {\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${\displaystyle ({\boldsymbol {\alpha }},S)}$ amb un vector de sortida denotat ${\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}$, el procés d'arribada té matriu generatriu,

${\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]}$

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.^[7] El cas homogeni té com a matriu de velocitat,

${\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 arribada de mida ${\displaystyle k}$ es produeix cada vegada que es produeix una transició a la submatriu ${\displaystyle D_{k}}$. Les submatrius ${\displaystyle D_{k}}$ tenen elements de ${\displaystyle \lambda _{i,j}}$, la velocitat d'un procés de Poisson, de manera que,

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

i

${\displaystyle \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ó.^[8]

Programari

• KPC-toolbox, una biblioteca de scripts MATLAB per adaptar-se a un mapa de dades.^[9]

Referències