matrix analytic method

An M/G/1-type stochastic matrix is one of the form

::$P\; =\; \backslash begin\{pmatrix\}$

B_0 & B_1 & B_2 & B_3 & \cdots \\

A_0 & A_1 & A_2 & A_3 & \cdots \\

& A_0 & A_1 & A_2 & \cdots \\

& & A_0 & A_1 & \cdots \\

\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.{{cite book|first1=Gunter|last1= Bolch|first2=Stefan |last2= Greiner |first3=Hermann |last3=de Meer |first4= Kishor |last4= Shridharbhai Trivedi | year=2006| edition=2 | page=250| title=Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications |publisher= John Wiley & Sons, Inc|isbn=978-0471565253}}{{Cite book | first1 = Jesús R. | last1 =Artalejo | first2 = Antonio | last2 = Gómez-Corral| doi = 10.1007/978-3-540-78725-9_7 | chapter = The Matrix-Analytic Formalism | title = Retrial Queueing Systems | pages = 187–205 | year = 2008 | isbn = 978-3-540-78724-2 }} If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations

::$P\; \backslash pi\; =\; \backslash pi\; \backslash quad\; \backslash text\{\; and\; \}\; \backslash quad\; \backslash mathbf\; e^\backslash text\{T\}\backslash 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\; =\; \backslash sum\_\{i=0\}^\backslash infty\; G^i\; A\_i.$

G is called the auxiliary matrix.{{Cite journal | last1 = Riska | first1 = A. | last2 = Smirni | first2 = E. | author2-link= Evgenia Smirni | doi = 10.1145/511399.511346 | title = Exact aggregate solutions for M/G/1-type Markov processes | journal = ACM SIGMETRICS Performance Evaluation Review | volume = 30 | pages = 86 | year = 2002 | citeseerx = 10.1.1.109.2225 }} Matrices are defined

::$\backslash begin\{align\}$

\overline{A}_{i+1} &= \sum_{j=i+1}^\infty G^{j-i-1}A_j \\

\overline{B}_i &= \sum_{j=i}^\infty G^{j-i}B_j

\end{align}

then π₀ is found by solving

::$\backslash begin\{align\}$

\overline{B}_0 \pi_0 &= \pi_0\\

\quad \left(\mathbf e^{\text{T}} + \mathbf e^{\text{T}}\left(I - \sum_{i=1}^\infty \overline{A}_i\right)^{-1}\sum_{i=1}^\infty \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.{{Cite journal | last1 = Ramaswami | first1 = V. | doi = 10.1080/15326348808807077 | title = A stable recursion for the steady state vector in markov chains of m/g/1 type | journal = Communications in Statistics. Stochastic Models | volume = 4 | pages = 183–188 | year = 1988 }}

::$\backslash pi\_i\; =\; (I-\backslash overline\{A\}\_1)^\{-1\}\; \backslash left[\; \backslash overline\{B\}\_\{i+1\}\; \backslash pi\_0\; +\; \backslash sum\_\{j=1\}^\{i-1\}\; \backslash overline\{A\}\_\{i+1-j\}\backslash pi\_j\; \backslash right],\; i\; \backslash geq\; 1.$

There are two popular iterative methods for computing G,{{Cite book | last1 = Bini | first1 = D. A. | last2 = Latouche | first2 = G. | last3 = Meini | first3 = B.|author3-link=Beatrice Meini | doi = 10.1093/acprof:oso/9780198527688.001.0001 | title = Numerical Methods for Structured Markov Chains | year = 2005 | isbn = 9780198527688 }}{{Cite journal | last1 = Meini | first1 = B. |author1-link=Beatrice Meini| doi = 10.1080/15326349808807483 | title = Solving m/g/l type markov chains: Recent advances and applications | journal = Communications in Statistics. Stochastic Models | volume = 14 | issue = 1–2 | pages = 479–496 | year = 1998 }}

• functional iterations
• cyclic reduction.

• [http://www.cs.wm.edu/MAMSolver/ MAMSolver]{{Cite book | last1 = Riska | first1 = A. | last2 = Smirni | first2 = E. | author2-link = Evgenia Smirni | chapter = MAMSolver: A Matrix Analytic Methods Tool | doi = 10.1007/3-540-46029-2_14 | title = Computer Performance Evaluation: Modelling Techniques and Tools | series = Lecture Notes in Computer Science | volume = 2324 | pages = 205 | year = 2002 | isbn = 978-3-540-43539-6 | citeseerx = 10.1.1.146.2080 }}

{{Reflist}}

{{Queueing theory}}

Category:Markov processes

Category:Single queueing nodes

Category:Probability theory