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, D0 and D1 where elements of D0 represent hidden transitions and elements of D1 observable transitions. The block matrix Q below is a transition rate matrix for a continuous-time Markov chain.

Q=[D0D100…0D0D10…00D0D1…⋮⋮⋱⋱⋱].

The simplest example is a Poisson process where D0 = −λ and D1 = λ 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 Di

0≤[D1]i,j<∞0≤[D0]i,j<∞i≠j[D0]i,i<0(D0+D1)1=0

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(𝜶,S) with an exit vector denoted 𝑺0=−S1, the arrival process has generator matrix,

Q=[S𝑺0𝜶00…0S𝑺0𝜶0…00S𝑺0𝜶…⋮⋮⋱⋱⋱]

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=[D0D1D2D3…0D0D1D2…00D0D1…⋮⋮⋱⋱⋱].

An arrival of size k occurs every time a transition occurs in the sub-matrix Dk. Sub-matrices Dk have elements of λi,j, the rate of a Poisson process, such that,

0≤[Dk]i,j<∞1≤k
0≤[D0]i,j<∞i≠j
[D0]i,i<0

and

∑k=0∞Dk1=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

D1=diag⁡{λ1,…,λm}D0=R−D1.

Fitting

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

Software

See also