Matrix analytic method explained

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

P = \begin{pmatrix} 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} & … \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}

where B_i and A_i 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

P \pi = \pi and e ^{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 π₁, π₂, π₃, …. To compute these probabilities the column stochastic matrix G is computed such that

G = \sum ^{inf ty} _{i =0} G ^{i} A _{i.}

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

\begin{align} \overline{A} _{i+1} & = \sum ^{inf ty} _{j = i +1} G ^{j-i-1} A _{j} \\ \overline{B} _{i} & = \sum ^{inf ty} _{j = i} G ^{j-i} B _{j \end{align}}

then π₀ is found by solving

\begin{align} \overline{B} _{0} \pi _{0} & = \pi _{0\\} \left( e ^{T} + e ^{T} \left(I - \sum ^{inf ty} _{i =1} \overline{A} ^{-1} _{i\right)} \sum ^{inf ty} _{i =1} \overline{B} _{i\right)} \pi _{0} & = 1 \end{align}

and the π_i are given by Ramaswami's formula, 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 ^{i -1} _{j =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.

Tools

• MAMSolver^[12]

Notes and References

1. Book: Harchol-Balter . M.. Mor Harchol-Balter . Phase-Type Distributions and Matrix-Analytic Methods . 10.1017/CBO9781139226424.028 . Performance Modeling and Design of Computer Systems . 359–379 . 2012 . 9781139226424 .
2. Neuts . M. F. . 10.1016/0377-2217(84)90034-1 . Matrix-analytic methods in queuing theory . European Journal of Operational Research . 15 . 2–12. 1984 .
3. Meini . B.. Beatrice Meini . An improved FFT-based version of Ramaswami's formula . 10.1080/15326349708807423 . Communications in Statistics. Stochastic Models . 13 . 2 . 223–238 . 1997 .
4. Stathopoulos . A. . Riska . A. . Hua . Z. . Smirni . E. . Evgenia Smirni . Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes . 10.1016/j.peva.2005.07.003 . Performance Evaluation . 62 . 1–4 . 331–348 . 2005 . 10.1.1.80.9473 .
5. Book: Riska . A. . Smirni . E. . Evgenia Smirni . M/G/1-Type Markov Processes: A Tutorial . 10.1007/3-540-45798-4_3 . Performance Evaluation of Complex Systems: Techniques and Tools . Lecture Notes in Computer Science . 2459 . 36 . 2002 . 978-3-540-44252-3 . http://www.cs.wm.edu/~riska/paper-MG1-tutorial.pdf . registration .
6. Book: Gunter. Bolch. Stefan . Greiner . Hermann . de Meer . Kishor . Shridharbhai Trivedi . 2006. 2 . 250. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications . John Wiley & Sons, Inc. 978-0471565253.
7. Book: Jesús R. . Artalejo . Antonio . Gómez-Corral. 10.1007/978-3-540-78725-9_7 . The Matrix-Analytic Formalism . Retrial Queueing Systems . 187–205 . 2008 . 978-3-540-78724-2 .
8. Riska . A. . Smirni . E. . Evgenia Smirni . 10.1145/511399.511346 . Exact aggregate solutions for M/G/1-type Markov processes . ACM SIGMETRICS Performance Evaluation Review . 30 . 86 . 2002 . 10.1.1.109.2225 .
9. Ramaswami . V. . 10.1080/15326348808807077 . A stable recursion for the steady state vector in markov chains of m/g/1 type . Communications in Statistics. Stochastic Models . 4 . 183–188 . 1988 .
10. Book: Bini . D. A. . Latouche . G. . Meini . B.. Beatrice Meini . 10.1093/acprof:oso/9780198527688.001.0001 . Numerical Methods for Structured Markov Chains . 2005 . 9780198527688 .
11. Meini . B. . Beatrice Meini. 10.1080/15326349808807483 . Solving m/g/l type markov chains: Recent advances and applications . Communications in Statistics. Stochastic Models . 14 . 1–2 . 479–496 . 1998 .
12. Book: Riska . A. . Smirni . E. . Evgenia Smirni . MAMSolver: A Matrix Analytic Methods Tool . 10.1007/3-540-46029-2_14 . Computer Performance Evaluation: Modelling Techniques and Tools . Lecture Notes in Computer Science . 2324 . 205 . 2002 . 978-3-540-43539-6 . 10.1.1.146.2080 .