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

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

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

Определение [ править ]

Марковский процесс поступления определяется двумя матрицами D ₀ и D _1, где элементы 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} & \ точки \\\ 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}} \ конец {выровнено}}}$

Особые случаи [ править ]

Пуассоновский процесс с марковской модуляцией [ править ]

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

${\ displaystyle {\ begin {align} D_ {1} & = \ operatorname {diag} \ {\ lambda _ {1}, \ dots, \ lambda _ {m} \} \\ D_ {0} & = R- D_ {1}. \ End {выравнивается}}}$

Фазовый процесс продления [ править ]

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

Пакетный процесс прибытия Маркова [ править ]

Партии марковского прибытия процесс ( ВМАР ) является обобщением марковского процесса прибытия, позволяя более одного прибытия на один раз. ^[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 k}$${\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}]_{i,i}<0\;}$

а также

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

Примерка [ править ]

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

Программное обеспечение [ править ]

• KPC-toolbox - это библиотека сценариев MATLAB для соответствия MAP данным. ^[9]

См. Также [ править ]

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

Ссылки [ править ]