Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Markovian arrival process
open-in-new
<h2 id="definition">Definition</h2> <p>A Markov arrival process is defined by two matrices, <i>D</i>0 and <i>D</i>1 where elements of <i>D</i>0 represent hidden transitions and elements of <i>D</i>1 observable transitions. The <a href="/facts/Block_matrix/fPI8HX9f">block matrix</a> <i>Q</i> below is a <a href="/facts/Transition_rate_matrix/6m9Tjrby">transition rate matrix</a> for a <a href="/facts/Continuous-time_Markov_chain/h7ytJ6p3">continuous-time Markov chain</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> 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]\;.} <p>The simplest example is a Poisson process where <i>D</i>0 = −<i>λ</i> and <i>D</i>1 = <i>λ</i> where there is only one possible transition, it is observable, and occurs at rate <i>λ</i>. For <i>Q</i> to be a valid transition rate matrix, the following restrictions apply to the <i>D</i><i>i</i> </p> 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}}} <h2 id="special-cases">Special cases</h2> <h3>Phase-type renewal process</h3> <p>The phase-type renewal process is a Markov arrival process with <a href="/facts/Phase-type_distribution/LGDbCMKh">phase-type distributed</a> 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, </p> Q = [ S S 0 α 0 0 … 0 S S 0 α 0 … 0 0 S S 0 α … ⋮ ⋮ ⋱ ⋱ ⋱ ] {\displaystyle 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]} <h2 id="generalizations">Generalizations</h2> <h3>Batch Markov arrival process</h3> <p>The batch Markovian arrival process (<i>BMAP</i>) is a generalisation of the Markovian arrival process by allowing more than one arrival at a time.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> <a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> The homogeneous case has rate matrix, </p> Q = [ D 0 D 1 D 2 D 3 … 0 D 0 D 1 D 2 … 0 0 D 0 D 1 … ⋮ ⋮ ⋱ ⋱ ⋱ ] . {\displaystyle 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]\;.} <p>An arrival of size k {\displaystyle k} occurs every time a transition occurs in the sub-matrix D k {\displaystyle D_{k}} . Sub-matrices D k {\displaystyle D_{k}} have elements of λ i , j {\displaystyle \lambda _{i,j}} , the rate of a <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a>, such that, </p> 0 ≤ [ D k ] i , j < ∞ 1 ≤ k {\displaystyle 0\leq [D_{k}]_{i,j}<\infty \;\;\;\;1\leq k} 0 ≤ [ D 0 ] i , j < ∞ i ≠ j {\displaystyle 0\leq [D_{0}]_{i,j}<\infty \;\;\;\;i\neq j} [ D 0 ] i , i < 0 {\displaystyle [D_{0}]_{i,i}<0\;} <p>and </p> ∑ k = 0 ∞ D k 1 = 0 {\displaystyle \sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}} <h3>Markov-modulated Poisson process</h3> <p>The Markov-modulated Poisson process or MMPP where <i>m</i> Poisson processes are switched between by an underlying <a href="/facts/Continuous-time_Markov_chain/h7ytJ6p3">continuous-time Markov chain</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> If each of the <i>m</i> Poisson processes has rate <i>λ</i><i>i</i> and the modulating continuous-time Markov has <i>m</i> × <i>m</i> transition rate matrix <i>R</i>, then the MAP representation is </p> D 1 = diag { λ 1 , … , λ m } D 0 = R − D 1 . {\displaystyle {\begin{aligned}D_{1}&=\operatorname {diag} \{\lambda _{1},\dots ,\lambda _{m}\}\\D_{0}&=R-D_{1}.\end{aligned}}} <h2 id="fitting">Fitting</h2> <p>A MAP can be fitted using an <a href="/facts/Expectation%25E2%2580%2593maximization_algorithm/32P2bdBc">expectation–maximization algorithm</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h3>Software</h3> <ul><li><a href="https://github.com/kpctoolboxteam/kpc-toolbox">KPC-toolbox</a> a library of <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> scripts to fit a MAP to data.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Rational_arrival_process/vWx35BG5">Rational arrival process</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Asmussen, S. R. (2003). "Markov Additive Models". Applied Probability and Queues. Stochastic Modelling and Applied Probability. Vol. 51. pp. 302–339. doi:10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8. <a href="978-0-387-00211-8" target="_blank">978-0-387-00211-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Asmussen, S. (2000). "Matrix-analytic Models and their Analysis". Scandinavian Journal of Statistics. 27 (2): 193–226. doi:10.1111/1467-9469.00186. JSTOR 4616600. S2CID 122810934. <a href="https://doi.org/10.1111%2F1467-9469.00186" target="_blank">https://doi.org/10.1111%2F1467-9469.00186</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Chakravarthy, S. R. (2011). "Markovian Arrival Processes". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0499. ISBN 9780470400531. <a href="9780470400531" target="_blank">9780470400531</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Asmussen, S. (2000). "Matrix-analytic Models and their Analysis". Scandinavian Journal of Statistics. 27 (2): 193–226. doi:10.1111/1467-9469.00186. JSTOR 4616600. S2CID 122810934. <a href="https://doi.org/10.1111%2F1467-9469.00186" target="_blank">https://doi.org/10.1111%2F1467-9469.00186</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Neuts, Marcel F. (1979). "A Versatile Markovian Point Process". Journal of Applied Probability. 16 (4). Applied Probability Trust: 764–779. doi:10.2307/3213143. JSTOR 3213143. S2CID 123525892. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Casale, G. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review. 39: 357. doi:10.1145/2007116.2007176. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Lucantoni, D. M. (1993). "The BMAP/G/1 queue: A tutorial". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. pp. 330–358. doi:10.1007/BFb0013859. ISBN 3-540-57297-X. S2CID 35110866. <a href="3-540-57297-X" target="_blank">3-540-57297-X</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Singh, Gagandeep; Gupta, U. C.; Chaudhry, M. L. (2016). "Detailed computational analysis of queueing-time distributions of the BMAP/G/1 queue using roots". Journal of Applied Probability. 53 (4): 1078–1097. doi:10.1017/jpr.2016.66. S2CID 27505255. <a href="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" target="_blank">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</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Fischer, W.; Meier-Hellstern, K. (1993). "The Markov-modulated Poisson process (MMPP) cookbook". Performance Evaluation. 18 (2): 149. doi:10.1016/0166-5316(93)90035-S. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Buchholz, P. (2003). "An EM-Algorithm for MAP Fitting from Real Traffic Data". Computer Performance Evaluation. Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2794. pp. 218–236. doi:10.1007/978-3-540-45232-4_14. ISBN 978-3-540-40814-7. <a href="978-3-540-40814-7" target="_blank">978-3-540-40814-7</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Casale, G.; Zhang, E. Z.; Smirni, E. (2008). "KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes" (PDF). 2008 Fifth International Conference on Quantitative Evaluation of Systems. p. 83. doi:10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5. S2CID 252444. <a href="978-0-7695-3360-5" target="_blank">978-0-7695-3360-5</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> </ol>