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.
An M/G/1-type stochastic matrix is one of the form
where B<sub>i</sub> and A<sub>i</sub> 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
where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, àis partitioned to ÃÂ<sub>1</sub>, ÃÂ<sub>2</sub>, ÃÂ<sub>3</sub>, â¦. To compute these probabilities the column stochastic matrix G is computed such that
G is called the auxiliary matrix. Matrices are defined
then ÃÂ<sub>0</sub> is found by solving
and the ÃÂ<sub>i</sub> are given by Ramaswami's formula, a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.
There are two popular iterative methods for computing G,