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.^[1][2] Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue.^[3][4] The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.^[5]

An M/G/1-type stochastic matrix is one of the form^[3]

${\displaystyle 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.^[6][7] If P is irreducible^{[broken anchor]} and positive recurrent then the stationary distribution is given by the solution to the equations^[3]

${\displaystyle 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 π₁, π₂, π₃, …. To compute these probabilities the column stochastic matrix G is computed such that^[3]

${\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}$

G is called the auxiliary matrix.^[8] Matrices are defined^[3]

${\displaystyle {\begin{aligned}{\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{aligned))}$

then π₀ is found by solving^[3]

${\displaystyle {\begin{aligned}{\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{aligned))}$

and the π_i are given by Ramaswami's formula,^[3] a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.^[9]

${\displaystyle \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.}$

There are two popular iterative methods for computing G,^[10][11]

• functional iterations
• cyclic reduction.

• MAMSolver^[12]

v t e Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson point process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job next Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean-field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category