probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, the matrix analytic method is a technique to compute the stationary

probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...

of a

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...

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 In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure. The method was developed "largely by ...

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 In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergence ...

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. ::

i \geq 1.

Computation of ''G''

There are two popular

iterative method In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived fr ...

s for computing ''G'', * functional iterations *

cyclic reduction Cyclic reduction is a numerical method for solving large linear systems by repeatedly splitting the problem. Each step eliminates even or odd rows and columns of a matrix and remains in a similar form. The elimination step is relatively expensive ...

Tools

MAMSolver
ref>

References

{{Queueing theory Markov processes Single queueing nodes Probability theory