Matrix analytic method

---

title: "Matrix analytic method" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["markov-processes", "single-queueing-nodes", "probability-theory"] description: "Computing technique in probability theory" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Matrix_analytic_method" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Computing technique in probability theory ::

In probability theory, the matrix analytic method is a technique to compute the stationary probability distribution of a Markov chain which has a repeating structure (after some point) and a state space which grows unboundedly in no more than one dimension. Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue. The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.

Method description

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

::P = \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. If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations

::P \pi = \pi \quad \text{ and } \quad \mathbf e^\text{T}\pi = 1

where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, π is partitioned to π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such that

:: G = \sum_{i=0}^\infty G^i A_i.

G is called the auxiliary matrix. Matrices are defined

::\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 π0 is found by solving

::\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.

::\pi_i = (I-\overline{A}1)^{-1} \left[ \overline{B}{i+1} \pi_0 + \sum_{j=1}^{i-1} \overline{A}_{i+1-j}\pi_j \right], i \geq 1.

Computation of ''G''

There are two popular iterative methods for computing G,

• functional iterations
• cyclic reduction.

Tools

• MAMSolver

References

References

1. (2012). "Performance Modeling and Design of Computer Systems".
2. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research.
3. (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models.
4. (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". Performance Evaluation.
5. (2002). "Performance Evaluation of Complex Systems: Techniques and Tools".
6. (2006). "Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications". John Wiley & Sons, Inc.
7. (2008). "Retrial Queueing Systems".
8. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review.
9. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". Communications in Statistics. Stochastic Models.
10. (2005). "Numerical Methods for Structured Markov Chains".
11. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models.
12. (2002). "Computer Performance Evaluation: Modelling Techniques and Tools".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::