Matrix geometric method

From HandWiki

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

[math]\displaystyle{ 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} }[/math]

where each of B00, B01, B10, A0, A1 and A2 are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors πi

[math]\displaystyle{ \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} }[/math]

Observe that the relationship

[math]\displaystyle{ \pi_i = \pi_1 R^{i-1} }[/math]

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

[math]\displaystyle{ \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} }[/math]

which can be solve to find π0 and π1 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

Main page: 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 = π1 Ri – 1 used above holds.[8]

External links

References

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



Retrieved from "https://handwiki.org/wiki/index.php?title=Matrix_geometric_method&oldid=3364347"