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

В теория вероятности, то матричный геометрический метод это метод анализа квазирождение – смерть, цепь Маркова с непрерывным временем чей матрицы скорости перехода с повторяющейся блочной структурой.^[1] Метод был разработан «в основном Марселем Ф. Нейтсом и его учениками, начиная примерно с 1975 года».^[2]

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

Для этого метода требуется матрица скорости перехода с трехдиагональный блочная структура следующим образом

${\displaystyle Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}}$

где каждый из B₀₀, B₀₁, B₁₀, А₀, А₁ и А₂ матрицы. Чтобы вычислить стационарное распределение π письмо π Q = 0 уравнения баланса рассматриваются для подвекторов π_я

${\displaystyle {\begin{aligned}\pi _{0}B_{00}+\pi _{1}B_{10}&=0\\\pi _{0}B_{01}+\pi _{1}A_{1}+\pi _{2}A_{0}&=0\\\pi _{1}A_{2}+\pi _{2}A_{1}+\pi _{3}A_{0}&=0\\&\vdots \\\pi _{i-1}A_{2}+\pi _{i}A_{1}+\pi _{i+1}A_{0}&=0\\&\vdots \\\end{aligned}}}$

Обратите внимание, что отношения

${\displaystyle \pi _{i}=\pi _{1}R^{i-1}}$

держит где р - матрица ставок Нейта,^[3] которые можно вычислить численно. Используя это, мы пишем

${\displaystyle {\begin{aligned}{\begin{pmatrix}\pi _{0}&\pi _{1}\end{pmatrix}}{\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}+RA_{0}\end{pmatrix}}={\begin{pmatrix}0&0\end{pmatrix}}\end{aligned}}}$

который можно решить, чтобы найти π₀ и π₁ и, следовательно, итеративно все π_я.

Расчет р

Матрица р можно вычислить, используя циклическое сокращение^[4] или логарифмическое сокращение.^[5][6]

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

Основная статья: Матричный аналитический метод

Матричный аналитический метод представляет собой более сложную версию матричного геометрического метода решения, используемого для анализа моделей с блочными M / G / 1 матрицы.^[7] Такие модели сложнее, потому что нет таких отношений, как π_я = π₁ р^я – 1 использованные выше удержания.^[8]

внешняя ссылка

• Моделирование производительности и цепи Маркова (часть 2) Уильям Дж. Стюарт в 7-я Международная школа формальных методов проектирования компьютерных, коммуникационных и программных систем: оценка эффективности

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

1. Харрисон, Питер Г.; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур. Эддисон-Уэсли. стр.317–322. ISBN  0-201-54419-9.
2. Асмуссен, С. Р. (2003). «Случайные прогулки». Прикладная вероятность и очереди. Стохастическое моделирование и прикладная вероятность. 51. С. 220–243. Дои:10.1007/0-387-21525-5_8. ISBN  978-0-387-00211-8.
3. Рамасвами, В. (1990). «Теорема двойственности для матричных парадигм в теории массового обслуживания». Коммуникации в статистике. Стохастические модели. 6: 151–161. Дои:10.1080/15326349908807141.
4. Bini, D .; Мейни, Б. (1996). «О решении нелинейного матричного уравнения, возникающего в задачах массового обслуживания». Журнал SIAM по матричному анализу и приложениям. 17 (4): 906. Дои:10.1137 / S0895479895284804.
5. Латуш, Гай; Рамасвами, В. (1993). "Алгоритм логарифмической редукции для процессов квази-рождения-смерти". Журнал прикладной теории вероятностей. Доверие прикладной вероятности. 30 (3): 650–674. JSTOR  3214773.
6. Pérez, J. F .; Ван Хоудт, Б. (2011). «Процессы квази-рождения и смерти с ограниченными переходами и их приложения» (PDF). Оценка эффективности. 68 (2): 126. Дои:10.1016 / j.peva.2010.04.003.
7. Альфа, А. С .; Рамасвами, В. (2011). «Матричный аналитический метод: обзор и история». Энциклопедия исследований операций и управления Wiley. Дои:10.1002 / 9780470400531.eorms0631. ISBN  9780470400531.
8. Болч, Гюнтер; Грейнер, Стефан; де Меер, Германн; Шридхарбхай Триведи, Кишор (2006). Сети массового обслуживания и марковские цепи: моделирование и оценка производительности с помощью компьютерных приложений (2-е изд.). John Wiley & Sons, Inc. стр. 259. ISBN  0471565253.