Abstract
Phase Type Distributions (PHDs) and Markovian Arrival Processes (MAPs) are established models in computational probability to describe random processes in stochastic models. In this paper we extend MAPs to Multi-Dimensional MAPs (MDMAPs) which are a model for random vectors that may be correlated in different dimensions. The computation of different quantities like joint moments or conditional densities is introduced and a first approach to compute parameters with respect to measured data is presented.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In an n-dimensional space elements are always numbered from 0 through \(n-1\) because this numbering is more appropriate for mapping multi-dimensional spaces into a single space.
- 2.
We use the names \(\textit{\textbf{D}}\) and \(\textit{\textbf{C}}\) rather than \(\textit{\textbf{D}}_0\) and \(\textit{\textbf{D}}_1\) for the matrices of a MAP because the numbers in the postfix are later used to denote matrices of different MAPs or PHDs.
References
Assaf, D., Langberg, N.A., Savits, T.H., Shaked, M.: Multivariate phase-type distributions. Oper. Res. 32(3), 688–702 (1984). https://doi.org/10.1287/opre.32.3.688
Bause, F., Buchholz, P., Kriege, J.: ProFiDo - the processes fitting toolkit dortmund. In: QEST 2010, Seventh International Conference on the Quantitative Evaluation of Systems, Williamsburg, Virginia, USA, 15–18 September 2010, pp. 87–96. IEEE Computer Society (2010). https://doi.org/10.1109/QEST.2010.20
Biller, B.: Copula-based multivariate input models for stochastic simulation. Oper. Res. 57(4), 878–892 (2009). https://doi.org/10.1287/opre.1080.0669
Biller, B.: Copula-based multivariate input modeling. Surv. Oper. Res. Manag. Sci. 17, 69–84 (2012)
Biller, B., Ghosh, S.: Multivariate input processes. In: Henderson, S.G., Nelson, B.L. (eds.) Handbook of OR & MS, vol. 13, pp. 123–152. Elsevier, Amsterdam (2006)
Biller, B., Nelson, B.L.: Modeling and generating multivariate time-series input processes using a vector autoregressive technique. ACM Trans. Model. Comput. Simul. 13(3), 211–237 (2003). https://doi.org/10.1145/937332.937333
Bladt, M., Nielsen, B.F.: On the construction of bivariate exponential distributions with an arbitrary correlation coefficient. Stoch. Model. 26(3), 295–308 (2010)
Buchholz, P., Felko, I., Kriege, J.: Transformation of acyclic phase type distributions for correlation fitting. In: Dudin, A., De Turck, K. (eds.) ASMTA 2013. LNCS, vol. 7984, pp. 96–111. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39408-9_8
Buchholz, P., Kemper, P., Kriege, J.: Multi-class Markovian arrival processes and their parameter fitting. Perform. Eval. 67(11), 1092–1106 (2010)
Buchholz, P., Kriege, J.: Approximate aggregation of Markovian models using alternating least squares. Perform. Eval. 73, 73–90 (2014). https://doi.org/10.1016/j.peva.2013.09.001
Buchholz, P., Kriege, J.: Fitting correlated arrival and service times and related queueing performance. Queueing Syst. 85(3–4), 337–359 (2017). https://doi.org/10.1007/s11134-017-9514-5
Buchholz, P., Kriege, J., Felko, I.: Input Modeling with Phase-Type Distributions and Markov Models - Theory and Applications. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06674-5
Buchholz, P., Telek, M.: Rational processes related to communicating Markov processes. J. Appl. Probab. 49(1), 40–59 (2012). https://doi.org/10.1017/S0021900200008858
Cario, M.C., Nelson, B.L.: Numerical methods for fitting and simulating autoregressive-to-anything processes. INFORMS J. Comput. 10(1), 72–81 (1998). https://doi.org/10.1287/ijoc.10.1.72
D’Alconzo, A., Drago, I., Morichetta, A., Mellia, M., Casas, P.: A survey on big data for network traffic monitoring and analysis. IEEE Trans. Netw. Serv. Manag. 16(3), 800–813 (2019). https://doi.org/10.1109/TNSM.2019.2933358
Dolgov, S., Savostyanov, D.V.: Alternating minimal energy methods for linear systems in higher dimensions. SIAM J. Sci. Comput. 36(5) (2014). https://doi.org/10.1137/140953289
Holtz, S., Rohwedder, T., Schneider, R.: The alternating linear scheme for tensor optimization in the tensor train format. SIAM J. Sci. Comput. 34(2) (2012). https://doi.org/10.1137/100818893
Hong, Y., Zhang, M., Meeker, W.Q.: Big data and reliability applications: the complexity dimension. J. Qual. Technol. 50(2), 135–149 (2018)
Horváth, G., Telek, M., Buchholz, P.: A MAP fitting approach with independent approximation of the inter-arrival time distribution and the lag-correlation. In: QEST, pp. 124–133. IEEE CS Press (2005)
Kriege, J., Buchholz, P.: Traffic modeling with phase-type distributions and VARMA processes. In: Agha, G., Van Houdt, B. (eds.) QEST 2016. LNCS, vol. 9826, pp. 295–310. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43425-4_20
Kroonenberg, P.M., Leeuw, J.D.: Principal component analysis of three-mode data by means of alternating least squares algorithms. Psychometrika 45, 69–97 (1980). https://doi.org/10.1007/BF02293599
Kulkarni, V.G.: A new class of multivariate phase type distributions. Oper. Res. 37(1), 151–158 (1989). https://doi.org/10.1287/opre.37.1.151
Law, A.M.: Simulation Modeling and Analysis, 5th edn. Mc Graw Hill, New York (2013)
Lawson, C.L., Hanson, R.J.: Solving Least Squares Problems. Classics in Applied Mathematics. SIAM (1995)
Lucantoni, D.M.: New results on the single server queue with a batch Markovian arrival process. Stoch. Model. 7(1), 1–46 (1991)
Mishra, D., Gunasekaran, A., Papadopoulos, T., Childe, S.J.: Big data and supply chain management: a review and bibliometric analysis. Ann. OR 270(1–2), 313–336 (2018). https://doi.org/10.1007/s10479-016-2236-y
Neuts, M.F.: A versatile Markovian point process. J. Appl. Probab. 16, 764–779 (1979)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models - An Algorithmic Approach. Johns Hopkins University Press, Baltimore (1981)
Rohwedder, T., Uschmajew, A.: On local convergence of alternating schemes for optimization of convex problems in the tensor train format. SIAM J. Numer. Anal. 51(2), 1134–1162 (2013). https://doi.org/10.1137/110857520
Stewart, W.J.: Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling. Princeton University Press, Princeton (2009)
Telek, M., Horváth, G.: A minimal representation of Markov arrival processes and a moments matching method. Perform. Eval. 64(9–12), 1153–1168 (2007)
Thümmler, A., Buchholz, P., Telek, M.: A novel approach for phase-type fitting with the EM algorithm. IEEE Trans. Dependable Secur. Comput. 3(3), 245–258 (2006)
Trivedi, K.S.: Probability and Statistics with Reliability, Queuing and Computer Science Applications, 2 edn. Wiley (2016). https://doi.org/10.1002/9781119285441
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
1 Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Blume, A., Buchholz, P., Scherbaum, C. (2020). Markovian Arrival Processes in Multi-dimensions. In: Gribaudo, M., Jansen, D.N., Remke, A. (eds) Quantitative Evaluation of Systems. QEST 2020. Lecture Notes in Computer Science(), vol 12289. Springer, Cham. https://doi.org/10.1007/978-3-030-59854-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-59854-9_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59853-2
Online ISBN: 978-3-030-59854-9
eBook Packages: Computer ScienceComputer Science (R0)