Markovian arrival process

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 Marcel F. 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{array}{ccccc}{D}_0& D_1& 0& 0& \dots \\ 0& D_0& D_1& 0& \dots \\ 0& 0& D_0& D_1& \dots \\ ⋮& ⋮& \ddots & \ddots & \ddots \end{array}\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{array}{rl}0\le [D_1{]}_{i,j}& <\mathrm{\infty }\\ 0\le [D_0{]}_{i,j}& <\mathrm{\infty }i\ne j\\ [D_0{]}_{i,i}& <0\\ (D_0+D_1)\mathit{1}& =\mathit{0}\end{array}$

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$(\mathit{\alpha },S)$ with an exit vector denoted ${\mathit{S}}^0=-S\mathit{1}$, the arrival process has generator matrix,

$Q=\left[\begin{array}{ccccc}S& {\mathit{S}}^0\mathit{\alpha }& 0& 0& \dots \\ 0& S& {\mathit{S}}^0\mathit{\alpha }& 0& \dots \\ 0& 0& S& {\mathit{S}}^0\mathit{\alpha }& \dots \\ ⋮& ⋮& \ddots & \ddots & \ddots \\ \end{array}\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{array}{ccccc}{D}_0& D_1& D_2& D_3& \dots \\ 0& D_0& D_1& D_2& \dots \\ 0& 0& D_0& D_1& \dots \\ ⋮& ⋮& \ddots & \ddots & \ddots \end{array}\right].$

An arrival of size $k$ occurs every time a transition occurs in the sub-matrix $D_k$. Sub-matrices $D_k$ have elements of ${\lambda }_{i,j}$, the rate of a Poisson process, such that,

$0\le [D_k{]}_{i,j}<\mathrm{\infty }1\le k$

$0\le [D_0{]}_{i,j}<\mathrm{\infty }i\ne j$

$[D_0{]}_{i,i}<0$

and

$\sum _{k=0}^{\mathrm{\infty }}{D}_k\mathit{1}=\mathit{0}$

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{array}{rl}{D}_1& =\mathrm{diag}\{{\lambda }_1,\dots ,{\lambda }_m\}\\ D_0& =R-D_1.\end{array}$

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