{{Short description|Method of analysis in probability theory}} 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 matrix has a repetitive block structure.<ref>{{cite book|first=Peter G.|last=Harrison|author-link=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison-Wesley|year=1992|pages=[https://archive.org/details/performancemodel0000harr/page/317 317–322]|isbn=0-201-54419-9|url-access=registration|url=https://archive.org/details/performancemodel0000harr/page/317}}</ref> The method was developed "largely by Marcel F. Neuts and his students starting around 1975."<ref>{{Cite book | first1 = S. R. | last1 = Asmussen| doi = 10.1007/0-387-21525-5_8 | chapter = Random Walks | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 220–243 | year = 2003 | isbn = 978-0-387-00211-8 }}</ref>

==Method description==

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

::<math>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 ''B''<sub>00</sub>, ''B''<sub>01</sub>, ''B''<sub>10</sub>, ''A''<sub>0</sub>, ''A''<sub>1</sub> and ''A''<sub>2</sub> are matrices. To compute the stationary distribution ''π'' writing ''π''&nbsp;''Q''&nbsp;=&nbsp;0 the balance equations are considered for sub-vectors ''π''<sub>''i''</sub>

::<math>\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>\pi_i = \pi_1 R^{i-1}</math>

holds where ''R'' is the Neuts' rate matrix,<ref>{{Cite journal | last1 = Ramaswami | first1 = V. | doi = 10.1080/15326349908807141 | title = A duality theorem for the matrix paradigms in queueing theory | journal = Communications in Statistics. Stochastic Models | volume = 6 | pages = 151–161 | year = 1990 }}</ref> which can be computed numerically. Using this we write

::<math>\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 ''π''<sub>0</sub> and ''π''<sub>1</sub> and therefore iteratively all the ''π''<sub>''i''</sub>.

==Computation of ''R''==

The matrix ''R'' can be computed using cyclic reduction<ref>{{Cite journal | last1 = Bini | first1 = D. | last2 = Meini | first2 = B.|author2-link=Beatrice Meini | doi = 10.1137/S0895479895284804 | title = On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems | journal = SIAM Journal on Matrix Analysis and Applications | volume = 17 | issue = 4 | pages = 906 | year = 1996 }}</ref> or logarithmic reduction.<ref>{{cite journal | year = 1993 | title = A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes | journal = Journal of Applied Probability | volume = 30 | issue = 3 | pages = 650–674 | publisher = Applied Probability Trust | jstor = 3214773 | first1 = Guy | last1 = Latouche | first2 = V. | last2 = Ramaswami}}</ref><ref>{{Cite journal | last1 = Pérez | first1 = J. F. | last2 = Van Houdt | first2 = B. | doi = 10.1016/j.peva.2010.04.003 | title = Quasi-birth-and-death processes with restricted transitions and its applications | journal = Performance Evaluation| volume = 68 | issue = 2 | pages = 126 | year = 2011 | url = http://www.doc.ic.ac.uk/~jperezbe/data/PerezVanHoudt_PEVA_2011.pdf| hdl = 10067/859850151162165141 | hdl-access = free }}</ref>

==Matrix analytic method==

{{Main|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.<ref>{{Cite book | last1 = Alfa | first1 = A. S. | last2 = Ramaswami | first2 = V. | doi = 10.1002/9780470400531.eorms0631 | chapter = Matrix Analytic Method: Overview and History | title = Wiley Encyclopedia of Operations Research and Management Science | year = 2011 | isbn = 9780470400531 }}</ref> Such models are harder because no relationship like ''π''<sub>''i''</sub>&nbsp;=&nbsp;''π''<sub>1</sub>&nbsp;R<sup>''i''&nbsp;&ndash;&nbsp;1</sup> used above holds.<ref>{{cite book|first1=Gunter|last1= Bolch|first2=Stefan |last2= Greiner |first3=Hermann |last3=de Meer |author4-link=Kishor S. Trivedi|first4= Kishor Shridharbhai|last4= Trivedi | year=2006| edition=2 | page=259| title=Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications |publisher= John Wiley & Sons, Inc|isbn=0471565253}}</ref>

==External links==

* [http://www.sti.uniurb.it/events/sfm07pe/slides/Stewart_2.pdf 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''

==References==

{{Reflist}}

{{Queueing theory}}

Category:Queueing theory Category:1975 introductions

{{probability-stub}}