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

Эта статья о процессах прибытия в очереди. Для двумерных процессов см. Марковский аддитивный процесс .

В теории массового обслуживания — дисциплине математической теории вероятностей — марковский процесс прибытия ( MAP или MArP). ) — это математическая модель времени между поступлением заданий в систему. Самый простой такой процесс — это процесс Пуассона , в котором время между каждым приходом распределено экспоненциально .

Эти процессы были впервые предложены Марселем Ф. Нойтсом в 1979 году.

Определение

Марковский процесс прибытия определяется двумя матрицами, D ₀ и D ₁ , где элементы D ₀ представляют скрытые переходы, а элементы наблюдаемых переходов D ₁ . Блочная матрица Q ниже представляет собой матрицу скорости перехода для цепи Маркова с непрерывным временем .

$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

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

Особые случаи

Процесс обновления фазового типа

Процесс обновления фазового типа представляет собой марковский процесс прибытия с распределенным временем пребывания между вступлениями фазового типа . Например, если процесс прибытия имеет распределение времени между прибытиями PH $({\boldsymbol {\alpha }},S)$ с вектором выхода, обозначенным ${\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}$, процесс прибытия имеет порождающую матрицу,

$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 ) является обобщением процесса марковского прибытия, допуская более одного прибытия одновременно. Однородный случай имеет матрицу ставок,

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

Прибытие размера $k$ происходит каждый раз, когда происходит переход в подматрице $D_{k}$. Подматрицы $D_{k}$ иметь элементы $\lambda _{i,j}$, скорость процесса Пуассона , такая что,

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

и

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

Марковско-модулированный процесс Пуассона

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

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

Примерка

MAP можно подобрать с использованием алгоритма максимизации ожидания .

Программное обеспечение

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

См. также

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