Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Matrix analytic method
open-in-new
<h2 id="method-description">Method description</h2> <p>An M/G/1-type stochastic matrix is one of the form<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> P = ( B 0 B 1 B 2 B 3 ⋯ A 0 A 1 A 2 A 3 ⋯ A 0 A 1 A 2 ⋯ A 0 A 1 ⋯ ⋮ ⋮ ⋮ ⋮ ⋱ ) {\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}}} <p>where <i>B</i><i>i</i> and <i>A</i><i>i</i> are <i>k</i> × <i>k</i> matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the <a href="/facts/Embedded_Markov_chain/5oP5hntk">embedded Markov chain</a> in an M/G/1 queue.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> If <i>P</i> is <a href="/facts/Markov_chain/5oP5hntk">irreducible</a> and <a href="/facts/Positive_recurrent/5oP5hntk">positive recurrent</a> then the stationary distribution is given by the solution to the equations<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> P π = π and e T π = 1 {\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1} <p>where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of <i>P</i>, <i>π</i> is partitioned to <i>π</i>1, <i>π</i>2, <i>π</i>3, …. To compute these probabilities the column stochastic matrix <i>G</i> is computed such that<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> G = ∑ i = 0 ∞ G i A i . {\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.} <p><i>G</i> is called the auxiliary matrix.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> Matrices are defined<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p> A ¯ i + 1 = ∑ j = i + 1 ∞ G j − i − 1 A j B ¯ i = ∑ j = i ∞ G j − i B j {\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}}} <p>then <i>π</i>0 is found by solving<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> B ¯ 0 π 0 = π 0 ( e T + e T ( I − ∑ i = 1 ∞ A ¯ i ) − 1 ∑ i = 1 ∞ B ¯ i ) π 0 = 1 {\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}}} <p>and the <i>π</i><i>i</i> are given by Ramaswami's formula,<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> π i = ( I − A ¯ 1 ) − 1 [ B ¯ i + 1 π 0 + ∑ j = 1 i − 1 A ¯ i + 1 − j π j ] , i ≥ 1. {\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.} <h2 id="computation-of-g">Computation of <i>G</i></h2> <p>There are two popular <a href="/facts/Iterative_method/uKMAJhEh">iterative methods</a> for computing <i>G</i>,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p> <ul><li>functional iterations</li> <li><a href="/facts/Cyclic_reduction/79MF9DAq">cyclic reduction</a>.</li></ul> <h2 id="tools">Tools</h2> <ul><li><a href="http://www.cs.wm.edu/MAMSolver/">MAMSolver</a><a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Harchol-Balter, M. (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. pp. 359–379. doi:10.1017/CBO9781139226424.028. ISBN 9781139226424. <a href="9781139226424" target="_blank">9781139226424</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Neuts, M. F. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research. 15: 2–12. doi:10.1016/0377-2217(84)90034-1. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Stathopoulos, A.; Riska, A.; Hua, Z.; Smirni, E. (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". Performance Evaluation. 62 (1–4): 331–348. CiteSeerX 10.1.1.80.9473. doi:10.1016/j.peva.2005.07.003. <a href="/wiki/Evgenia_Smirni" target="_blank">/wiki/Evgenia_Smirni</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Riska, A.; Smirni, E. (2002). "M/G/1-Type Markov Processes: A Tutorial" (PDF). Performance Evaluation of Complex Systems: Techniques and Tools. Lecture Notes in Computer Science. Vol. 2459. pp. 36. doi:10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3. <a href="978-3-540-44252-3" target="_blank">978-3-540-44252-3</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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 ed.). John Wiley & Sons, Inc. p. 250. ISBN 978-0471565253. <a href="978-0471565253" target="_blank">978-0471565253</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Artalejo, Jesús R.; Gómez-Corral, Antonio (2008). "The Matrix-Analytic Formalism". Retrial Queueing Systems. pp. 187–205. doi:10.1007/978-3-540-78725-9_7. ISBN 978-3-540-78724-2. <a href="978-3-540-78724-2" target="_blank">978-3-540-78724-2</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Riska, A.; Smirni, E. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review. 30: 86. CiteSeerX 10.1.1.109.2225. doi:10.1145/511399.511346. <a href="/wiki/Evgenia_Smirni" target="_blank">/wiki/Evgenia_Smirni</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Meini, B. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. doi:10.1080/15326349708807423. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Ramaswami, V. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". Communications in Statistics. Stochastic Models. 4: 183–188. doi:10.1080/15326348808807077. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Bini, D. A.; Latouche, G.; Meini, B. (2005). Numerical Methods for Structured Markov Chains. doi:10.1093/acprof:oso/9780198527688.001.0001. ISBN 9780198527688. <a href="9780198527688" target="_blank">9780198527688</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Meini, B. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models. 14 (1–2): 479–496. doi:10.1080/15326349808807483. <a href="/wiki/Beatrice_Meini" target="_blank">/wiki/Beatrice_Meini</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Riska, A.; Smirni, E. (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2324. p. 205. CiteSeerX 10.1.1.146.2080. doi:10.1007/3-540-46029-2_14. ISBN 978-3-540-43539-6. <a href="978-3-540-43539-6" target="_blank">978-3-540-43539-6</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> </ol>