Markovian arrival process

Quality 0.50 · 1 view · Updated 2 months ago

Mathematical model in queueing theory

title: "Markovian arrival process" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["queueing-theory", "markov-processes"] description: "Mathematical model in queueing theory" topic_path: "general/queueing-theory" source: "https://en.wikipedia.org/wiki/Markovian_arrival_process" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Mathematical model in queueing theory ::

::callout[type=note] arrival processes to queues ::

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=\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 D**i

:\begin{align} 0\leq [D_{1}]{i,j}& 0\leq [D{0}]{i,j}& , [D{0}]{i,i}& (D{0}+D_{1})\boldsymbol{1} &= \boldsymbol{0} \end{align}

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

: 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]

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{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]; .

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\leq [D_{k}]_{i,j}

: 0\leq [D_{0}]_{i,j}

: [D_{0}]_{i,i}

and : \sum^{\infty}{k=0}D{k}\boldsymbol{1}=\boldsymbol{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{align} D_{1} &= \operatorname{diag}{\lambda_{1},\dots,\lambda_{m}}\ D_{0} &=R-D_1. \end{align}

Fitting

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

Software

References

References

  1. (2003). "Applied Probability and Queues".
  2. (2000). "Matrix-analytic Models and their Analysis". Scandinavian Journal of Statistics.
  3. (2011). "Wiley Encyclopedia of Operations Research and Management Science".
  4. (1979). "A Versatile Markovian Point Process". Applied Probability Trust.
  5. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review.
  6. (1993). "Performance Evaluation of Computer and Communication Systems".
  7. (2016). "Detailed computational analysis of queueing-time distributions of the BMAP/G/1 queue using roots". Journal of Applied Probability.
  8. (1993). "The Markov-modulated Poisson process (MMPP) cookbook". Performance Evaluation.
  9. (2003). "Computer Performance Evaluation. Modelling Techniques and Tools".
  10. (2008). "2008 Fifth International Conference on Quantitative Evaluation of Systems".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

queueing-theorymarkov-processes