In
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 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
::
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
::
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 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
MAMSolverref>
References
{{Queueing theory
Markov processes
Single queueing nodes
Probability theory