行列解析法

Computing technique in probability theory

確率論において、行列解析法は、ある時点以降に繰り返し構造を持ち、状態空間が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{ 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{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}}}$

π _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

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

• 機能的な反復
• 巡回削減。

ツール

• MAMSolver ^[12]

参考文献

1. Harchol-Balter, M. (2012). 「位相型分布と行列解析法」.コンピュータシステムのパフォーマンスモデリングと設計. pp.  359– 379. doi :10.1017/CBO9781139226424.028. ISBN 9781139226424。
2. Neuts, MF (1984). 「待ち行列理論における行列分析法」.ヨーロッパオペレーションズリサーチジャーナル. 15 : 2–12 . doi :10.1016/0377-2217(84)90034-1.
3. Meini, B. (1997). 「Ramaswamiの公式の改良FFTベース版」. Communications in Statistics. Stochastic Models . 13 (2): 223– 238. doi :10.1080/15326349708807423.
4. スタソポロス、A.;リスカ、A.華、Z。スミルニ、E. (2005)。 「M/G/1 タイプのプロセスを解決するための ETAQA とラマス​​ワミの公式の橋渡し」。性能評価。62 ( 1 ～ 4): 331 ～ 348。CiteSeerX 10.1.1.80.9473。土井：10.1016/j.peva.2005.07.003。 
5. Riska, A.; Smirni, E. (2002). 「M/G/1型マルコフ過程：チュートリアル」(PDF) .複雑系のパフォーマンス評価：手法とツール. コンピュータサイエンス講義ノート. 第2459巻. pp. 36. doi :10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3。
6. Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (第2版). John Wiley & Sons, Inc. p. 250. ISBN 978-0471565253。
7. アルタレホ、ヘスス R.;ゴメス＝コラル、アントニオ (2008)。 「マトリックス分析形式主義」。再審キューシステム。 pp.  187–205。土井:10.1007/978-3-540-78725-9_7。ISBN 978-3-540-78724-2。
8. Riska, A.; Smirni, E. (2002). 「M/G/1型マルコフ過程の正確な集約解」. ACM SIGMETRICSパフォーマンス評価レビュー. 30:86 . CiteSeerX 10.1.1.109.2225 . doi :10.1145/511399.511346. 
9. Ramaswami, V. (1988). 「m/g/1型マルコフ連鎖における定常状態ベクトルの安定再帰」. Communications in Statistics. Stochastic Models . 4 : 183–188 . doi :10.1080/15326348808807077.
10. ダビデ州ビニ;ラトゥーシュ、G.メイニ、B. (2005)。構造化マルコフ連鎖の数値的手法。土井：10.1093/acprof:oso/9780198527688.001.0001。ISBN 9780198527688。
11. Meini, B. (1998). 「m/g/l型マルコフ連鎖の解法：最近の進歩と応用」. Communications in Statistics. Stochastic Models . 14 ( 1–2 ): 479– 496. doi :10.1080/15326349808807483.
12. Riska, A.; Smirni, E. (2002). 「MAMSolver: 行列解析手法ツール」.コンピュータパフォーマンス評価：モデリング手法とツール. コンピュータサイエンス講義ノート. 第2324巻. p. 205. CiteSeerX 10.1.1.146.2080 . doi :10.1007/3-540-46029-2_14. ISBN  978-3-540-43539-6。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Matrix_analytic_method&oldid=1283051879"