Matrix analytic methods in applied probability with a view towards engineering applications
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.
Contents
Eighth international conference on matrix analytic methods in stochastic models inauguration
Method description
An M/G/1-type stochastic matrix is one of the form
where Bi and Ai 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 π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such that
G is called the auxiliary matrix. Matrices are defined
then π0 is found by solving
and the πi are given by Ramaswami's formula, a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.
Computation of G
There are two popular iterative methods for computing G,