Fine Art


In probability theory, the matrix analytic method is a technique to compute the stationary probability distribution of a Markov chain which has a repeating structure (after some point) and a state space which grows unboundedly in no more than one dimension.[1][2] Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue.[3][4] The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.[5]

Method description

An M/G/1-type stochastic matrix is one of the form[3]

\( 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} \)

where Bi and Ai are k × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the embedded Markov chain in an M/G/1 queue.[6][7] If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations[3]

\( P \pi = \pi \quad \text{ and } \quad \mathbf e^\text{T}\pi = 1 \)

where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, π is partitioned to π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such that[3]

\( G = \sum_{i=0}^\infty G^i A_i. \)

G is called the auxiliary matrix.[8] Matrices are defined[3]

\( \begin{align} \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{align} \)

then π0 is found by solving[3]

\( \begin{align} \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{align} \)

and the πi are given by Ramaswami's formula,[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.[9]

\( \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. \)

Computation of G

There are two popular iterative methods for computing G,[10][11]

functional iterations
cyclic reduction.




Harchol-Balter, M. (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. p. 359. doi:10.1017/CBO9781139226424.028. ISBN 9781139226424. edit
Neuts, M. F. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research 15: 2–0. doi:10.1016/0377-2217(84)90034-1. edit
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. edit
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: 331. doi:10.1016/j.peva.2005.07.003. edit
Riska, A.; Smirni, E. (2002). "M/G/1-Type Markov Processes: A Tutorial". Performance Evaluation of Complex Systems: Techniques and Tools (PDF). Lecture Notes in Computer Science 2459. p. 36. doi:10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3. edit
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 0471565253.
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. edit
Riska, A.; Smirni, E. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review 30: 86. doi:10.1145/511399.511346. edit
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. edit
Bini, D. A.; Latouche, G.; Meini, B. (2005). "Numerical Methods for Structured Markov Chains". doi:10.1093/acprof:oso/9780198527688.001.0001. ISBN 9780198527688. edit
Meini, B. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models 14: 479–496. doi:10.1080/15326349808807483. edit
Riska, A.; Smirni, E. (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science 2324. p. 205. doi:10.1007/3-540-46029-2_14. ISBN 978-3-540-43539-6.

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

Retrieved from ""
All text is available under the terms of the GNU Free Documentation License

Home - Hellenica World