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 = \begin 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$

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 \quad \mathbf e^\text\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_^\infty G^i A_i.$

''G'' is called the auxiliary matrix. Matrices are defined

::$\begin \overline_ &= \sum_^\infty G^A_j \\ \overline_i &= \sum_^\infty G^B_j \end$

then ''π''₀ is found by solving

::$\begin \overline_0 \pi_0 &= \pi_0\\ \quad \left(\mathbf e^ + \mathbf e^\left(I - \sum_^\infty \overline_i\right)^\sum_^\infty \overline_i\right) \pi_0 &= 1 \end$

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

::\pi_i = (I-\overline_1)^ \left \overline_ \pi_0 + \sum_^ \overline_\pi_j \right i \geq 1.

Computation of ''G''

There are two popular iterative methods for computing ''G'',
* functional iterations
* cyclic reduction.

Tools

MAMSolver
ref>

References

{{Queueing theory

Markov processes
Single queueing nodes
Probability theory