Markovian arrival process


In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process 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 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.
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

Special cases

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

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 with an exit vector denoted, the arrival process has generator matrix,

Batch Markov arrival process

The batch Markovian arrival process is a generalisation of the Markovian arrival process by allowing more than one arrival at a time. The homogeneous case has rate matrix,
An arrival of size occurs every time a transition occurs in the sub-matrix. Sub-matrices have elements of, the rate of a Poisson process, such that,
and

Fitting

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

Software