Matrix analytic method

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=\left(\begin{array}{ccccc}{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 \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$

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 \text{ and }{𝐞}^{\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

$G=\sum _{i=0}^{\mathrm{\infty }}{G}^i{A}_i.$

G is called the auxiliary matrix. Matrices are defined

$\begin{array}{cc}{\bar{A}}_{i+1}& =\sum _{j=i+1}^{\mathrm{\infty }}{G}^{j-i-1}{A}_j\\ {\bar{B}}_i& =\sum _{j=i}^{\mathrm{\infty }}{G}^{j-i}{B}_j\end{array}$

then π₀ is found by solving

$\begin{array}{cc}{\bar{B}}_0{\pi }_0& ={\pi }_0\\ ({𝐞}^{\text{T}}+{𝐞}^{\text{T}}{(I-\sum _{i=1}^{\mathrm{\infty }}{\bar{A}}_i)}^{-1}\sum _{i=1}^{\mathrm{\infty }}{\bar{B}}_i){\pi }_0& =1\end{array}$

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

${\pi }_i=(I-{\bar{A}}_1{)}^{-1}[{\bar{B}}_{i+1}{\pi }_0+\sum _{j=1}^{i-1}{\bar{A}}_{i+1-j}{\pi }_j],i\ge 1.$

Computation of G

There are two popular iterative methods for computing G,

• functional iterations
• cyclic reduction.

Tools

• MAMSolver