Markovian arrival processes

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

In queuing theory, Markovian arrival processes are used to model the arrival of customers to a queue.

Some of the most common include the Poisson process, Markovian arrival process and the batch Markovian arrival process.

1 Background
2 Poisson process
3 Markov arrival process
- 3.1 Markov-modulated Poisson process
- 3.2 Phase-type renewal process
4 Batch Markov arrival process
5 References

Background

Markovian arrival processes have two processes. A continuous-time Markov process $j (t),$ a Markov process which is generated by a generator or rate matrix, $Q$ . The other process is a counting process $N (t)$ , which has state space $\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$ (where $\mathbb{N}$ is the set of all natural numbers). $N (t)$ increases every time there is a transition in $j (t)$ that is marked.

Poisson process

The Poisson arrival process or Poisson process counts the number of arrivals, each of which has a exponentially distributed time between arrival. In the most general case this can be represented by the rate matrix,

$Q=\left[\begin{matrix} -\lambda_{0}&\lambda_{0}&0&0&\dots\\ 0&-\lambda_{1}&\lambda_{1}&0&\dots\\ 0&0&-\lambda_{2}&\lambda_{2}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .$

In the homogeneous case this is more simply,

$Q=\left[\begin{matrix} -\lambda&\lambda&0&0&\dots\\ 0&-\lambda&\lambda&0&\dots\\ 0&0&-\lambda&\lambda&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .$

Here every transition is marked.

Markov arrival process

The Markov arrival process (MAP) is a generalization of the Poisson process by having non-exponential distribution sojourn between arrivals. The homogeneous case has rate matrix,

$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]\; .$

An arrival is seen every time a transition occurs that increases the level (a marked transition), e.g. a transition in the $D 1$ sub-matrix. Sub-matrices $D 0$ and $D 1$ have elements of $λ i, j$ , the rate of a Poisson process, such that,

$0\leq [D_{1}]_{i,j}<\infty$

$0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j$

$[D_{0}]_{i,i}<0\;$

and

$(D_{0}+D_{1})\boldsymbol{1}=\boldsymbol{0}$

There are several special cases of the Markov arrival process.

Markov-modulated Poisson process

The Markov-modulated Poisson process or MMPP where $m$ Poisson processes are switched between by an underlying Markov process. If each of the $m$ Poisson processes has rate $λ i$ and the underlying process is generated by a $m\times m$ generator matrix $R$ , then in the MAP representation,

$D_{1} = \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}$

a diagonal matrix of the rates of the Poisson process, and

D 0 = R - D 1

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

Batch Markov arrival process

The batch Markovian arrival process (BMAP) is a generalisation of the Markovian arrival process by having arrivals of size greater than one. 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 $λ i, j$ , the rate of a Poisson process, such that,

$0\leq [D_{k}]_{i,j}<\infty\;\;\;\; 1\leq k$

$0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j$

$[D_{0}]_{i,i}<0\;$

and

$\sum^{\infty}_{k=0}D_{k}\boldsymbol{1}=\boldsymbol{0}$

References

This article or section includes a list of references or external links, but its sources remain unclear because it lacks in-text citations.
You can improve this article by introducing more precise citations where appropriate. (December 2007)

Søren Asmussen (2000). Matrix-analytic Models and their Analysis, Scandinavian Journal of Statistics 27(2), 193–226.
David M. Lucantoni (1993). The BMAP/G/1 Queue: A Tutorial, Lecture Notes in Computer Science: Performance Evaluation of Computer and Communication Systems (Editors: Lorenzo Donatiello and Randolph Nelson), volume 729.

Retrieved from "http://en.wikipedia.org/wiki/Markovian_arrival_processes"