{{Short description|Mathematical model in queueing theory}} {{About|arrival processes to queues|bivariate processes|Markov additive process}} In queueing theory, a discipline within the mathematical theory of probability, a '''Markovian arrival process''' ('''MAP''' or '''MArP'''<ref>{{Cite book | first1=S. R. |last1=Asmussen| doi = 10.1007/0-387-21525-5_11 | chapter = Markov Additive Models | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 302–339 | year = 2003 | isbn = 978-0-387-00211-8 }}</ref>) 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.<ref name="asmussen">{{Cite journal | last1 = Asmussen | first1 = S. | title = Matrix-analytic Models and their Analysis | doi = 10.1111/1467-9469.00186 | journal = Scandinavian Journal of Statistics | volume = 27 | issue = 2 | pages = 193–226 | year = 2000 | jstor = 4616600| s2cid = 122810934 | doi-access = free }}</ref><ref>{{Cite book | last1 = Chakravarthy | first1 = S. R. | chapter = Markovian Arrival Processes | doi = 10.1002/9780470400531.eorms0499 | title = Wiley Encyclopedia of Operations Research and Management Science | year = 2011 | isbn = 9780470400531 }}</ref>

The processes were first suggested by Marcel F. Neuts in 1979.<ref name="asmussen" /><ref>{{cite journal | last1 = Neuts | first1 = Marcel F. | year = 1979 | title = A Versatile Markovian Point Process | journal = Journal of Applied Probability | volume = 16 | issue = 4 | pages = 764–779 | publisher = Applied Probability Trust | jstor = 3213143 | doi = 10.2307/3213143 | s2cid = 123525892 }}</ref>

==Definition==

A Markov arrival process is defined by two matrices, ''D''<sub>0</sub> and ''D''<sub>1</sub> where elements of ''D''<sub>0</sub> represent hidden transitions and elements of ''D''<sub>1</sub> observable transitions. The block matrix ''Q'' below is a transition rate matrix for a continuous-time Markov chain.<ref>{{Cite journal | last1 = Casale | first1 = G. | doi = 10.1145/2007116.2007176 | title = Building accurate workload models using Markovian arrival processes | journal = ACM SIGMETRICS Performance Evaluation Review | volume = 39 | pages = 357 | year = 2011 }}</ref>

:<math> 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]\; .</math>

The simplest example is a Poisson process where ''D''<sub>0</sub>&nbsp;=&nbsp;−''λ'' and ''D''<sub>1</sub>&nbsp;=&nbsp;''λ'' 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''<sub>''i''</sub>

:<math>\begin{align} 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{align}</math>

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

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

==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.<ref>{{Cite book | last1 = Lucantoni | first1 = D. M. | chapter = The BMAP/G/1 queue: A tutorial | doi = 10.1007/BFb0013859 | title = Performance Evaluation of Computer and Communication Systems | series = Lecture Notes in Computer Science | volume = 729 | pages = 330–358 | year = 1993 | isbn = 3-540-57297-X | s2cid = 35110866 }}</ref><ref>{{cite journal |last1=Singh |first1=Gagandeep |last2=Gupta |first2=U. C. |last3=Chaudhry |first3=M. L. |title=Detailed computational analysis of queueing-time distributions of the BMAP/G/1 queue using roots |journal=Journal of Applied Probability |date=2016 |volume=53 |issue=4 |pages=1078–1097 |doi=10.1017/jpr.2016.66 |s2cid=27505255 |url=https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/detailed-computational-analysis-of-queueingtime-distributions-of-the-bmapg1-queue-using-roots/740DBCF255AFE602075EDB174FF0F25D|url-access=subscription }}</ref> The homogeneous case has rate matrix,

:<math> 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]\; .</math>

An arrival of size <math>k</math> occurs every time a transition occurs in the sub-matrix <math>D_{k}</math>. Sub-matrices <math>D_{k}</math> have elements of <math>\lambda_{i,j}</math>, the rate of a Poisson process, such that,

:<math> 0\leq [D_{k}]_{i,j}<\infty\;\;\;\; 1\leq k </math>

:<math> 0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j </math>

:<math> [D_{0}]_{i,i}<0\; </math>

and :<math> \sum^{\infty}_{k=0}D_{k}\boldsymbol{1}=\boldsymbol{0} </math>

=== 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.<ref>{{Cite journal |last1=Fischer |first1=W. |last2=Meier-Hellstern |first2=K. |year=1993 |title=The Markov-modulated Poisson process (MMPP) cookbook |journal=Performance Evaluation |volume=18 |issue=2 |pages=149 |doi=10.1016/0166-5316(93)90035-S}}</ref> If each of the ''m'' Poisson processes has rate ''λ''<sub>''i''</sub> and the modulating continuous-time Markov has ''m''&nbsp;×&nbsp;''m'' transition rate matrix ''R'', then the MAP representation is

:<math>\begin{align} D_{1} &= \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}\\ D_{0} &=R-D_1. \end{align}</math>

==Fitting==

A MAP can be fitted using an expectation–maximization algorithm.<ref>{{Cite book | last1 = Buchholz | first1 = P. | chapter = An EM-Algorithm for MAP Fitting from Real Traffic Data | doi = 10.1007/978-3-540-45232-4_14 | title = Computer Performance Evaluation. Modelling Techniques and Tools | series = Lecture Notes in Computer Science | volume = 2794 | pages = 218–236 | year = 2003 | isbn = 978-3-540-40814-7 }}</ref>

===Software=== * [https://github.com/kpctoolboxteam/kpc-toolbox KPC-toolbox] a library of MATLAB scripts to fit a MAP to data.<ref>{{Cite book | last1 = Casale | first1 = G. | last2 = Zhang | first2 = E. Z. | last3 = Smirni | first3 = E. | author3-link = Evgenia Smirni | doi = 10.1109/QEST.2008.33 | chapter = KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes | title = 2008 Fifth International Conference on Quantitative Evaluation of Systems | pages = 83 | year = 2008 | isbn = 978-0-7695-3360-5 | s2cid = 252444 | chapter-url = http://www.doc.ic.ac.uk/~gcasale/qest08kpctoolbox.pdf}}</ref>

==See also==

*Rational arrival process ==References== {{Reflist}}

{{Queueing theory}}

Category:Queueing theory Category:Markov processes