Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-13T14:02:11.121Z Has data issue: false hasContentIssue false
  • English
  • Français

Rational Processes Related to Communicating Markov Processes

Part of:Stochastic processesMarkov processes

Published online by Cambridge University Press:  04 February 2016

Peter Buchholz and
Miklós Telek
Peter Buchholz*
Affiliation:
TU Dortmund
Miklós Telek*
Affiliation:
Technical University of Budapest
*
∗ Postal address: Informatik IV, TU Dortmund, D-44221 Dortmund, Germany. Email address: peter.buchholz@udo.edu
∗∗ Postal address: Department of Telecommunications, Technical University of Budapest, H-1521 Budapest, Hungary. Email address: telek@hit.hme.hu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We define a class of stochastic processes, denoted as marked rational arrival processes (MRAPs), which is an extension of matrix exponential distributions and rational arrival processes. Continuous-time Markov processes with labeled transitions are a subclass of this more general model class. New equivalence relations between processes are defined, and it is shown that these equivalence relations are natural extensions of strong and weak lumpability and the corresponding bisimulation relations that have been defined for Markov processes. If a general rational process is equivalent to a Markov process, it can be used in numerical analysis techniques instead of the Markov process. This observation allows one to apply MRAPs like Markov processes and since the new equivalence relations are more general than lumpability and bisimulation, it is sometimes possible to find smaller representations of given processes. Finally, we show that the equivalence is preserved by the composition of MRAPs and can therefore be exploited in compositional modeling.

Keywords

Markov processrational processequivalencelumpability

MSC classification

Primary:60G20: Generalized stochastic processes
Secondary:60J27: Continuous-time Markov processes on discrete state spaces

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 1 , March 2012, pp. 40 - 59
Copyright
© Applied Probability Trust 

References

Akar, N. (2006). Solving the {ME/ME/1} queue with state-space methods and the matrix sign function. Performance Evaluation 63, 131–145.CrossRefGoogle Scholar
Asmussen, S. and Bladt, M. (1999). Point processes with finite-dimensional conditional probabilities. Stoch. Process. Appl. 82, 127–142.Google Scholar
Asmussen, S. and O'Cinneide, C. A. (1997). Matrix-exponential distributions—distributions with a rational Laplace transform. In Encyclopedia of Statistical Sciences, eds Kotz, S. and Read, C. B., John Wiley, New York, pp. 435–440.Google Scholar
Bean, N. G. and Nielsen, B. F. (2010). Quasi-birth-and-death processes with rational arrival process components. Stoch. Models 26, 309–334.Google Scholar
Buchholz, P. (1994). A class of hierarchical queueing networks and their analysis. Queueing Systems 15, 59–80.Google Scholar
Buchholz, P. (1994). Exact and ordinary lumpability in finite Markov chains. J. Appl. Prob. 31, 59–80.Google Scholar
Buchholz, P. (1995). Equivalence relations for stochastic automata networks. In Computations with Markov Chains, ed. Stewart, W. J., Kluwer, pp. 197–216.CrossRefGoogle Scholar
Buchholz, P. (2008). Bisimulation relations for weighted automata. Theoret. Comput. Sci. 393, 109–123.CrossRefGoogle Scholar
Buchholz, P. and Telek, M. (2010). Stochastic Petri nets with matrix exponentially distributed firing times. Performance Evaluation 67, 1373–1385.Google Scholar
Buchholz, P. and Telek, M. (2011). On minimal representations of rational arrival processes. Ann. Operat. Res. 24 pp.Google Scholar
De Schutter, B. (2000). Minimal state-space realization in linear system theory: an overview. J. Comput. Appl. Math. 121, 331–354.CrossRefGoogle Scholar
Fackrell, M. (2005). Fitting with matrix-exponential distributions. Stoch. Models 21, 377–400.CrossRefGoogle Scholar
He, Q.-M. and Neuts, M. F. (1998). Markov chains with marked transitions. Stoch. Process. Appl. 74, 37–52.Google Scholar
He, Q.-M. and Zhang, H. (2007). On matrix exponential distributions. Adv. Appl. Prob. 39, 271–292.CrossRefGoogle Scholar
Hermanns, H. (2002). Interactive Markov Chains. (Lecture Notes Comput. Sci. 2428). Springer, Berlin.Google Scholar
Hillston, J. (1995). Compositional Markovian modelling using a process algebra. In Computations with Markov Chains, ed. Stewart, W. J., Kluwer, pp. 177–196.Google Scholar
Horváth, A., Rácz, S. and Telek, M. (2009). Moments characterization of the class of order 3 matrix exponential distributions. In 16th Internat. Conf. on Analytical and Stochastic Modeling Techniques and Applications (Lecture Notes Comput. Sci. 5513), Springer, Berlin, pp. 174–188.Google Scholar
Kemeny, J. G. and Snell, J. L. (1976). Finite Markov Chains. Springer, New York.Google Scholar
Lipsky, L. (2008). Queueing Theory. Springer, New York.Google Scholar
Mitchell, K. (2001). Constructing a correlated sequence of matrix exponentials with invariant first-order properties. Operat. Res. Lett. 28, 27–34.CrossRefGoogle Scholar
Neuts, M. F. (1979). A versatile Markovian point process. J. Appl. Prob. 16, 764–779.CrossRefGoogle Scholar
Park, D. (1981). Concurrency and automata on infinite sequences. In Theoretical Computer Science (Lecture Notes Comput. Sci. 104), Springer, pp. 167–183.Google Scholar
Rubino, G. and Sericola, B. (1993). A finite characterization of weak lumpable Markov processes. II. The continuous time case. Stoch. Process. Appl. 45, 115–125.CrossRefGoogle Scholar
Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press.Google Scholar
Telek, M. and Horváth, G. (2007). A minimal representation of Markov arrival processes and a moments matching method. Performance Evaluation 64, 1153–1168.CrossRefGoogle Scholar
Wu, S.-H., Smolka, S. A. and Stark, E. W. (1997). Composition and behaviors of probabilistic {I/O} automata. Theoret. Comput. Sci. 176, 1–38.CrossRefGoogle Scholar