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

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

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

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

Определение

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

${displaystyle Q=left[{egin{matrix}D_{0}&D_{1}&0&0&dots �&D_{0}&D_{1}&0&dots �&0&D_{0}&D_{1}&dots vdots &vdots &ddots &ddots &ddots end{matrix}}ight];.}$

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

${displaystyle {egin{aligned}0leq [D_{1}]_{i,j}&<infty �leq [D_{0}]_{i,j}&<infty quad ieq j,[D_{0}]_{i,i}&<0(D_{0}+D_{1}){oldsymbol {1}}&={oldsymbol {0}}end{aligned}}}$

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

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

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

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

Фазовый процесс обновления

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

${displaystyle Q=left[{egin{matrix}S&{oldsymbol {S}}^{0}{oldsymbol {alpha }}&0&0&dots �&S&{oldsymbol {S}}^{0}{oldsymbol {alpha }}&0&dots �&0&S&{oldsymbol {S}}^{0}{oldsymbol {alpha }}&dots vdots &vdots &ddots &ddots &ddots end{matrix}}ight]}$

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

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

${displaystyle Q=left[{egin{matrix}D_{0}&D_{1}&D_{2}&D_{3}&dots �&D_{0}&D_{1}&D_{2}&dots �&0&D_{0}&D_{1}&dots vdots &vdots &ddots &ddots &ddots end{matrix}}ight];.}$

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

${displaystyle 0leq [D_{k}]_{i,j}<infty ;;;;1leq k}$

${displaystyle 0leq [D_{0}]_{i,j}<infty ;;;;ieq j}$

${displaystyle [D_{0}]_{i,i}<0;}$

и

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

Установка

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

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

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

Смотрите также

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

использованная литература

1. Асмуссен, С. Р. (2003). «Марковские аддитивные модели». Прикладная вероятность и очереди. Стохастическое моделирование и прикладная вероятность. 51. С. 302–339. Дои:10.1007/0-387-21525-5_11. ISBN  978-0-387-00211-8.
2. Асмуссен, С. (2000). «Матрично-аналитические модели и их анализ». Скандинавский статистический журнал. 27 (2): 193–226. Дои:10.1111/1467-9469.00186. JSTOR  4616600.
3. Чакраварти, С. Р. (2011). «Марковские процессы прихода». Энциклопедия исследований операций и управления Wiley. Дои:10.1002 / 9780470400531.eorms0499. ISBN  9780470400531.
4. Neuts, Марсель Ф. (1979). «Универсальный марковский точечный процесс». Журнал прикладной теории вероятностей. Доверие прикладной вероятности. 16 (4): 764–779. Дои:10.2307/3213143. JSTOR  3213143.
5. Казале, Г. (2011). «Построение точных моделей нагрузки с использованием марковских процессов прибытия». Обзор оценки эффективности ACM SIGMETRICS. 39: 357. Дои:10.1145/2007116.2007176.
6. Фишер, В .; Мейер-Хельштерн, К. (1993). "Поваренная книга Марково-модулированного процесса Пуассона (MMPP)". Оценка эффективности. 18 (2): 149. Дои:10.1016 / 0166-5316 (93) 90035-S.
7. Лукантони, Д. М. (1993). «Очередь BMAP / G / 1: учебное пособие». Оценка производительности компьютерных и коммуникационных систем. Конспект лекций по информатике. 729. С. 330–358. Дои:10.1007 / BFb0013859. ISBN  3-540-57297-X.
8. Бухгольц, П. (2003). "EM-алгоритм подбора MAP по данным реального трафика". Оценка производительности компьютера. Методы и инструменты моделирования. Конспект лекций по информатике. 2794. С. 218–236. Дои:10.1007/978-3-540-45232-4_14. ISBN  978-3-540-40814-7.
9. Casale, G .; Zhang, E. Z .; Смирни, Э. (2008). "KPC-Toolbox: простая, но эффективная подгонка трассировки с использованием марковских процессов прибытия" (PDF). 2008 Пятая Международная конференция по количественной оценке систем. п. 83. Дои:10.1109 / QEST.2008.33. ISBN  978-0-7695-3360-5.