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

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

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

Стохастическая матрица типа M/G/1 имеет один из видов

$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 _i и A _i — матрицы размера k × k . (Обратите внимание, что неотмеченные элементы матрицы представляют нули.) Такая матрица описывает встроенную цепь Маркова в очереди M/G/1. Если P неприводим ​ и положительно-рекуррентное , то стационарное распределение задаётся решением уравнений

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

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

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

G называется вспомогательной матрицей. Матрицы определены

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

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

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

и π _i определяются по формуле Рамасвами : численно стабильное соотношение, впервые опубликованное Вайдьянатаном Рамасвами в 1988 году.

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

Вычисление G

Существует два популярных итерационных метода вычисления G :

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

Инструменты

• МАМсолвер