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 = [ D 0 D 1 0 0 … 0 D 0 D 1 0 … 0 0 D 0 D 1 … ⋮ ⋮ ⋱ ⋱ ⋱ ] . {\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]\;.}
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 ≤ [ D 1 ] i , j < ∞ 0 ≤ [ D 0 ] i , j < ∞ i ≠ j [ D 0 ] i , i < 0 ( D 0 + D 1 ) 1 = 0 {\displaystyle {\begin{aligned}0\leq [D_{1}]_{i,j}&<\infty \\0\leq [D_{0}]_{i,j}&<\infty \quad i\neq j\\\,[D_{0}]_{i,i}&<0\\(D_{0}+D_{1}){\boldsymbol {1}}&={\boldsymbol {0}}\end{aligned}}}
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 ) {\displaystyle ({\boldsymbol {\alpha }},S)} with an exit vector denoted S 0 = − S 1 {\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}} , the arrival process has generator matrix,
… excerpt ends here. Continue reading the full article.
