Matrix geometric method: Difference between revisions

Revision as of 17:32, 5 June 2013

Latest revision as of 06:51, 10 May 2024

(30 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Method of analysis in probability theory}}

In [[probability theory]], the '''matrix geometric solution method''' is a method for the analysis of [[quasi-birth–death process]]es, [[continuous-time MarokovMarkov chainschain]] whose [[transition rate matrices]] with a repetitive block structure.<ref>{{cite book|first=Peter G.|last=Harrison|authorlinkauthor-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-322 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>{{citeCite book doi| 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==

Line 14 ⟶ 15:

\end{pmatrix}</math>

where each of ''B''₀₀, ''B''₀₁, ''B''₁₀, ''A''₀, ''A''₁ and ''A''₂ are matrices. To compute the stationary distribution ''π'' writing ''π''&nbsp;''Q''&nbsp;=&nbsp;0 the [[balance equation]]s are considered for sub-vectors ''π''_''i''

To compute the stationary distribution ''π'' writing ''π''&nbsp;''Q''&nbsp;=&nbsp;0 the [[balance equation]]s are considered for sub-vectors ''π''_''i''

::<math>\begin{align}

\pi_0 B_{00} + \pi_1 B_{10} &= 0\\

\pi_0 B_{01} + \pi_1 A_1 + \pi_2 A0A_0 &= 0\\

\pi_1 A_2 + \pi_2 A_1 + \pi_3 A_0 &= 0 \\

\vdots & \vdots \\

\pi_{i-1} A_2 + \pi_i A_1 + \pi_{i+1} A_0 &= 0\\

\vdots & \vdots \\

\end{align}</math>

Observe that the relationship

Observe that the relationship ''π''_''i''&nbsp;=&nbsp;''π''₁&nbsp;R^{''i''&nbsp;&ndash;&nbsp;1} holds where ''R'' is the Neut's rate matrix,<ref>{{cite doi|10.1080/15326349908807141}}</ref> which can be computed numerically. Using this we write

::<math>\pi_i = \pi_1 R^{i-1}</math>

holds where ''R'' is the Neut's 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}

Line 36 ⟶ 39:

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]]<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 queue|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 ''π''_''i''&nbsp;=&nbsp;''π''₁&nbsp;R^{''i''&nbsp;&ndash;&nbsp;1} 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==

Line 41 ⟶ 57:

{{Reflist}}

{{Queueing theory}}

{{probability-stub}}

[[Category:Queueing theory]]

[[Category:1975 introductions]]

{{probability-stub}}