Matrix geometric method explained

In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure.^[1] The method was developed "largely by Marcel F. Neuts and his students starting around 1975."^[2]

Method description

The method requires a transition rate matrix with tridiagonal block structure as follows

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}

where each of B₀₀, B₀₁, B₁₀, A₀, A₁ and A₂ are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors π_i

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

Observe that the relationship

\pi _{i} = \pi _{1} R ^{i-1}

holds where R is the Neut's rate matrix,^[3] which can be computed numerically. Using this we write

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

which can be solve to find π₀ and π₁ and therefore iteratively all the π_i.

Computation of R

The matrix R can be computed using cyclic reduction^[4] or logarithmic reduction.^{[5] [6]}

Matrix analytic method

See main article: Matrix analytic method. The matrix analytic method is a more complicated version of the matrix geometric solution method used to analyse models with block M/G/1 matrices.^[7] Such models are harder because no relationship like π_i = π₁ R^{i  -  1} used above holds.^[8]

External links

• Performance Modelling and Markov Chains (part 2) by William J. Stewart at 7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation

Notes and References

1. Book: Harrison, Peter G.. Peter G. Harrison. Naresh M.. Patel. Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. 1992. 317–322. 0-201-54419-9. registration.
2. Book: S. R. . Asmussen. 10.1007/0-387-21525-5_8 . Random Walks . Applied Probability and Queues . Stochastic Modelling and Applied Probability . 51 . 220–243 . 2003 . 978-0-387-00211-8 .
3. Ramaswami . V. . 10.1080/15326349908807141 . A duality theorem for the matrix paradigms in queueing theory . Communications in Statistics. Stochastic Models . 6 . 151–161 . 1990 .
4. Bini . D. . Meini . B.. Beatrice Meini . 10.1137/S0895479895284804 . On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems . SIAM Journal on Matrix Analysis and Applications . 17 . 4 . 906 . 1996 .
5. 1993 . A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes . Journal of Applied Probability . 30 . 3 . 650–674 . Applied Probability Trust . 3214773 . Guy . Latouche . V. . Ramaswami.
6. Pérez . J. F. . Van Houdt . B. . 10.1016/j.peva.2010.04.003 . Quasi-birth-and-death processes with restricted transitions and its applications . Performance Evaluation. 68 . 2 . 126 . 2011 . 10067/859850151162165141 . free .
7. Book: Alfa . A. S. . Ramaswami . V. . 10.1002/9780470400531.eorms0631 . Matrix Analytic Method: Overview and History . Wiley Encyclopedia of Operations Research and Management Science . 2011 . 9780470400531 .
8. Book: Gunter. Bolch. Stefan . Greiner . Hermann . de Meer . Kishor S. Trivedi. Kishor Shridharbhai. Trivedi . 2006. 2 . 259. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications . John Wiley & Sons, Inc. 0471565253.