行列幾何学的方法

確率論において、行列幾何学的方法は、反復ブロック構造を持つ遷移率行列を持つ連続時間マルコフ連鎖である準誕生-死亡過程を分析する方法である。 ^[1]この方法は、「主に1975年頃からマルセル・F・ノイツと彼の学生によって」開発された。 ^[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 ₁₀、A ₀、A ₁、A ₂はそれぞれ行列である。定常分布πを計算するためにπ  Q  = 0と書き、部分ベクトルπ _iについてバランス方程式が考慮される。

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

が成り立ち、Rはニュートの速​​度行列^[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}}}$

これを解くとπ ₀とπ ₁が見つかり、したがってすべてのπ _{i が}反復的に見つかります。

行列Rは巡回減算^[4]または対数減算^{[5] [6]}を使用して計算できます。

行列解析法は、ブロックM/G/1行列モデルを解析するために使用される行列幾何解法のより複雑なバージョンです。^{[7]このようなモデルは、上で使用した}π _i  =  π ₁  R ^{i  – 1}のような関係が成立しないため、より困難です。^[8]

• パフォーマンスモデリングとマルコフ連鎖（パート2）第7回国際スクール「コンピュータ、通信、ソフトウェアシステムの設計のための形式手法：パフォーマンス評価」におけるウィリアム・J・スチュワートによる講演