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.

[math]\displaystyle{ Q=\left[\begin{matrix} D_{0}&D_{1}&0&0&\dots\\ 0&D_{0}&D_{1}&0&\dots\\ 0&0&D_{0}&D_{1}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; . }[/math]

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

[math]\displaystyle{ \begin{align} 0\leq [D_{1}]_{i,j}&\lt \infty \\ 0\leq [D_{0}]_{i,j}&\lt \infty \quad i\neq j \\ \, [D_{0}]_{i,i}&\lt 0 \\ (D_{0}+D_{1})\boldsymbol{1} &= \boldsymbol{0} \end{align} }[/math]

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[math]\displaystyle{ (\boldsymbol{\alpha},S) }[/math] with an exit vector denoted [math]\displaystyle{ \boldsymbol{S}^{0}=-S\boldsymbol{1} }[/math], the arrival process has generator matrix,

[math]\displaystyle{ Q=\left[\begin{matrix} S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&0&\dots\\ 0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&\dots\\ 0&0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&\dots\\ \vdots&\vdots&\ddots&\ddots&\ddots\\ \end{matrix}\right] }[/math]

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,

[math]\displaystyle{ Q=\left[\begin{matrix} D_{0}&D_{1}&D_{2}&D_{3}&\dots\\ 0&D_{0}&D_{1}&D_{2}&\dots\\ 0&0&D_{0}&D_{1}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; . }[/math]

An arrival of size [math]\displaystyle{ k }[/math] occurs every time a transition occurs in the sub-matrix [math]\displaystyle{ D_{k} }[/math]. Sub-matrices [math]\displaystyle{ D_{k} }[/math] have elements of [math]\displaystyle{ \lambda_{i,j} }[/math], the rate of a Poisson process, such that,

[math]\displaystyle{ 0\leq [D_{k}]_{i,j}\lt \infty\;\;\;\; 1\leq k }[/math]

[math]\displaystyle{ 0\leq [D_{0}]_{i,j}\lt \infty\;\;\;\; i\neq j }[/math]

[math]\displaystyle{ [D_{0}]_{i,i}\lt 0\; }[/math]

and

[math]\displaystyle{ \sum^{\infty}_{k=0}D_{k}\boldsymbol{1}=\boldsymbol{0} }[/math]

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

[math]\displaystyle{ \begin{align} D_{1} &= \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}\\ D_{0} &=R-D_1. \end{align} }[/math]

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