Markovian Arrival Processes

In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process (MAP or MArP) is a mathematical model for the time between job arrivals to a system. The simplest such process is a Poisson process where the time between each arrival is exponentially distributed.

The processes were first suggested by Neuts in 1979.

Definition

A Markov arrival process is defined by two matrices, ''D''₀ and ''D''₁ where elements of ''D''₀ represent hidden transitions and elements of ''D''₁ observable transitions. The block matrix ''Q'' below is a transition rate matrix for a continuous-time Markov chain.

:
Q=\left begin
D_&D_&0&0&\dots\\
0&D_&D_&0&\dots\\
0&0&D_&D_&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end\right; .

The simplest example is a Poisson process where ''D''₀ = −''λ'' and ''D''₁ = ''λ'' where there is only one possible transition, it is observable, and occurs at rate ''λ''. For ''Q'' to be a valid transition rate matrix, the following restrictions apply to the ''D''_''i''

:\begin
0\leq _&<\infty \\
0\leq _&<\infty \quad i\neq j \\
\, _&<0 \\
(D_+D_)\boldsymbol &= \boldsymbol
\end

Special cases

Phase-type renewal process

The phase-type renewal process is a Markov arrival process with phase-type distributed sojourn between arrivals. For example, if an arrival process has an interarrival time distribution PH$(\boldsymbol,S)$ with an exit vector denoted $\boldsymbol^=-S\boldsymbol$, the arrival process has generator matrix,

:
Q=\left begin
S&\boldsymbol^\boldsymbol&0&0&\dots\\
0&S&\boldsymbol^\boldsymbol&0&\dots\\
0&0&S&\boldsymbol^\boldsymbol&\dots\\
\vdots&\vdots&\ddots&\ddots&\ddots\\
\end\right

Generalizations

Batch Markov arrival process

The batch Markovian arrival process (''BMAP'') is a generalisation of the Markovian arrival process by allowing more than one arrival at a time. The homogeneous case has rate matrix,

:
Q=\left begin
D_&D_&D_&D_&\dots\\
0&D_&D_&D_&\dots\\
0&0&D_&D_&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end\right; .

An arrival of size $k$ occurs every time a transition occurs in the sub-matrix $D_$. Sub-matrices $D_$ have elements of $\lambda_$, the rate of a Poisson process, such that,

:
0\leq _<\infty\;\;\;\; 1\leq k

:
0\leq _<\infty\;\;\;\; i\neq j

:
_<0\;

and
:$\sum^_D_\boldsymbol=\boldsymbol$

Markov-modulated Poisson process

The Markov-modulated Poisson process or MMPP where ''m'' Poisson processes are switched between by an underlying continuous-time Markov chain. If each of the ''m'' Poisson processes has rate ''λ''_''i'' and the modulating continuous-time Markov has ''m'' × ''m'' transition rate matrix ''R'', then the MAP representation is

:$\begin D_ &= \operatorname\\\ D_ &=R-D_1. \end$

Fitting

A MAP can be fitted using an expectation–maximization algorithm.

Software

KPC-toolbox
a library of MATLAB scripts to fit a MAP to data.

See also

* Rational arrival process

References

{{Queueing theory

Queueing theory
Markov processes