Матричный аналитический метод - Matrix analytic method

В теория вероятности, то матричный аналитический метод представляет собой метод вычисления стационарного распределения вероятностей цепи Маркова, которая имеет повторяющуюся структуру (после некоторой точки) и пространство состояний, которое неограниченно растет не более чем в одном измерении.^[1][2] Такие модели часто описывают как Цепи Маркова типа M / G / 1 потому что они могут описывать переходы в очереди M / G / 1.^[3][4] Метод представляет собой более сложную версию матричный геометрический метод и является классическим методом решения цепочек M / G / 1.^[5]

Описание метода

Стохастическая матрица типа M / G / 1 имеет вид^[3]

${\displaystyle P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}$

куда B_я и А_я находятся k × k матрицы. (Обратите внимание, что неотмеченные элементы матрицы представляют нули.) Такая матрица описывает встроенная цепь Маркова в очереди M / G / 1.^[6][7] Если п является несводимый и положительный повторяющийся то стационарное распределение дается решением уравнений^[3]

${\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}$

куда е представляет собой вектор подходящей размерности со всеми значениями, равными 1. Соответствие структуре п, π разделен на π₁, π₂, π₃,…. Для вычисления этих вероятностей столбцовая стохастическая матрица грамм вычисляется так, что^[3]

${\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}$

грамм называется вспомогательной матрицей.^[8] Матрицы определены^[3]

${\displaystyle {\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}}$

тогда π₀ находится путем решения^[3]

${\displaystyle {\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}}$

и π_я даны Формула Рамасвами,^[3] численно стабильные отношения, впервые опубликованные Вайдьянатаном Рамасвами в 1988 году.^[9]

${\displaystyle \pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.}$

Расчет грамм

Есть два популярных итерационные методы для вычислений грамм,^[10][11]

• функциональные итерации
• циклическое сокращение.

Инструменты

• MAMSolver^[12]

Рекомендации

1. Харчол-Балтер, М. (2012). «Фазовые распределения и матрично-аналитические методы». Моделирование производительности и проектирование компьютерных систем. С. 359–379. Дои:10.1017 / CBO9781139226424.028. ISBN  9781139226424.
2. Нейтс, М. Ф. (1984). «Матрично-аналитические методы в теории массового обслуживания». Европейский журнал операционных исследований. 15: 2–12. Дои:10.1016/0377-2217(84)90034-1.
3. Мейни, Б. (1997). «Улучшенная версия формулы Рамасвами на основе БПФ». Коммуникации в статистике. Стохастические модели. 13 (2): 223–238. Дои:10.1080/15326349708807423.
4. Stathopoulos, A .; Риска, А .; Hua, Z .; Смирни, Э. (2005). «Соединение ETAQA и формулы Рамасвами для решения процессов типа M / G / 1». Оценка эффективности. 62 (1–4): 331–348. CiteSeerX  10.1.1.80.9473. Дои:10.1016 / j.peva.2005.07.003.
5. Риска, А .; Смирни, Э. (2002). "Марковские процессы типа M / G / 1: Учебное пособие" (PDF). Оценка эффективности сложных систем: методы и инструменты. Конспект лекций по информатике. 2459. стр.36. Дои:10.1007/3-540-45798-4_3. ISBN  978-3-540-44252-3.
6. Болч, Гюнтер; Грейнер, Стефан; де Меер, Германн; Шридхарбхай Триведи, Кишор (2006). Сети массового обслуживания и марковские цепи: моделирование и оценка производительности с помощью компьютерных приложений (2-е изд.). John Wiley & Sons, Inc. стр. 250. ISBN  978-0471565253.
7. Artalejo, Jesús R .; Гомес-Корраль, Антонио (2008). «Матрично-аналитический формализм». Системы очередей повторных испытаний. С. 187–205. Дои:10.1007/978-3-540-78725-9_7. ISBN  978-3-540-78724-2.
8. Риска, А .; Смирни, Э. (2002). «Точные агрегированные решения для марковских процессов типа M / G / 1». Обзор оценки эффективности ACM SIGMETRICS. 30: 86. CiteSeerX  10.1.1.109.2225. Дои:10.1145/511399.511346.
9. Рамасвами, В. (1988). «Стабильная рекурсия для вектора установившегося состояния в марковских цепях типа m / g / 1». Коммуникации в статистике. Стохастические модели. 4: 183–188. Дои:10.1080/15326348808807077.
10. Бини, Д. А .; Latouche, G .; Мейни, Б. (2005). Численные методы для структурированных цепей Маркова.. Дои:10.1093 / acprof: oso / 9780198527688.001.0001. ISBN  9780198527688.
11. Мейни, Б. (1998). «Решение цепей Маркова типа m / g / l: последние достижения и применения». Коммуникации в статистике. Стохастические модели. 14 (1–2): 479–496. Дои:10.1080/15326349808807483.
12. Риска, А .; Смирни, Э. (2002). «MAMSolver: инструмент для матричных аналитических методов». Оценка производительности компьютера: методы и инструменты моделирования. Конспект лекций по информатике. 2324. п. 205. CiteSeerX  10.1.1.146.2080. Дои:10.1007/3-540-46029-2_14. ISBN  978-3-540-43539-6.