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

В теории вероятностей , то матрица аналитический метод представляет собой метод для вычисления стационарного распределения вероятностей цепи Маркова , которая имеет повторяющуюся структуру (после того, как какие - то момент) и пространство состояний , которое растет неограниченно не более чем в одном измерения. ^{[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 _i и A _i - матрицы размера k  ×  k . (Обратите внимание, что неотмеченные элементы матрицы представляют нули.) Такая матрица описывает вложенную цепь Маркова в очередь M / G / 1. ^{[6] [7]} Если Р является неприводимым и положительным рецидивирующий то стационарное распределение задается решение уравнений ^[3]

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

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

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

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

${\ displaystyle {\ begin {align} {\ overline {A}} _ {i + 1} & = \ sum _ {j = i + 1} ^ {\ infty} G ^ {ji-1} A_ {j} \\ {\ overline {B}} _ {i} & = \ sum _ {j = i} ^ {\ infty} G ^ {ji} B_ {j} \ end {выровнено}}}$

тогда π ₀ находится путем решения ^[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}}}$

и π _я определяются формулой Ramaswami в , ^[3] стабильные отношения численно впервые опубликован Vaidyanathan Ramaswami в 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.}$

Вычисление G [ править ]

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

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

Инструменты [ править ]

• MAMSolver ^[12]

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