行列解析法

確率論において、行列解析法は、（ある時点以降に）繰り返し構造を持ち、1次元以下で無制限に成長する状態空間を持つマルコフ連鎖の定常確率分布を計算する手法である。 ^{[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]} Pが既約^{[壊れたアンカー]}で正の再帰的である場合、定常分布は方程式の解によって与えられる^[3]

${\displaystyle P\pi =\pi \quad {\text{ および }}\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{aligned}{\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{aligned}}}$

π _0は^[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}}}$

π _{i は}ラマスワミの公式^[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.}$

Gを計算するための一般的な反復法は2つある。^{[10] [11]}

• 機能的な反復
• 循環削減。

• MAMSolver ^[12]