Марковский процесс прибытия

В теории очередей , дисциплине в математической теории вероятностей , марковский процесс прибытия ( МАР или МАРП ^[1] ) представляет собой математическую модель для времени между прибытиями заданий в систему. Простейшим таким процессом является процесс Пуассона , где время между каждым прибытием распределено экспоненциально . ^{[2] [3]}

Впервые эти процессы были предложены Марселем Ф. Ньютсом в 1979 году. ^{[2] [4]}

Марковский процесс прибытия определяется двумя матрицами, D ₀ и D ₁ , где элементы D ₀ представляют скрытые переходы, а элементы D ₁ — наблюдаемые переходы. Приведенная ниже блочная матрица Q — это матрица скорости перехода для непрерывной по времени цепи Маркова . ^[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]\;.}$

Простейшим примером является процесс Пуассона, где D ₀  = − λ и D ₁  =  λ , где есть только один возможный переход, он наблюдаем и происходит со скоростью λ . Для того чтобы Q была допустимой матрицей скорости перехода, к D _i применяются следующие ограничения

${\displaystyle {\begin{align}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{align}}}$

Процесс обновления фазового типа — это марковский процесс прибытия с распределенным пребыванием фазового типа между прибытиями. Например, если процесс прибытия имеет распределение времени между прибытиями PH с вектором выхода, обозначенным , процесс прибытия имеет матрицу генератора,${\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]}$

Пакетный марковский процесс прибытия ( BMAP ) является обобщением марковского процесса прибытия, допускающим более одного прибытия за раз. ^{[6] [7]} Однородный случай имеет матрицу скоростей,

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

Приход размера происходит каждый раз, когда в подматрице происходит переход . Подматрицы имеют элементы , скорость процесса Пуассона , такие, что,${\displaystyle к}$${\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}]_{я,я}<0\;}$

и

${\displaystyle \sum _{k=0}^{\infty }D_ {k}{\boldsymbol {1}} = {\boldsymbol {0}}}$

Марковско -модулированный процесс Пуассона или MMPP , где m пуассоновских процессов переключаются между собой с помощью базовой цепи Маркова с непрерывным временем . ^[8] Если каждый из m пуассоновских процессов имеет скорость λ _i , а модулирующий марковский процесс с непрерывным временем имеет матрицу скорости перехода R размером m  ×  m , то представление MAP имеет вид

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

MAP можно подогнать с помощью алгоритма максимизации ожидания . ^[9]

• KPC-toolbox — библиотека скриптов MATLAB для подгонки MAP к данным. ^[10]

• Рациональный процесс прибытия