Abstract
In the literature, the notions of lumpability and time reversibility for large Markov chains have been widely used to efficiently study the functional and non-functional properties of computer systems. In this paper we explore the relations among different definitions of lumpability (strong, exact and strict) and the notion of time-reversed Markov chain. Specifically, we prove that an exact lumping induces a strong lumping on the reversed Markov chain and a strict lumping holds both for the forward and the reversed processes. Based on these results we introduce the class of \(\lambda \rho \)-reversible Markov chains which combines the notions of lumping and time reversibility modulo state renaming. We show that the class of autoreversible processes, previously introduced in Marin and Rossi (Proceedings of the IEEE 21st international symposium on modeling, analysis and simulation of computer and telecommunication systems MASCOTS, pp. 151–160, 2013), is strictly contained in the class of \(\lambda \rho \)-reversible chains.
Similar content being viewed by others
References
Baarir, S., Beccuti, M., Dutheillet, C., Franceschinis, G., Haddad, S.: Lumping partially symmetrical stochastic models. Perform. Eval. 68(1), 21–44 (2011)
Baier, C., Haverkort, B., Hermanns, H., Katoen, J.P.: Model-checking algorithms for continuous-time Markov chains. IEEE Trans. Soft. Eng. 29(7), 524–541 (2003)
Balsamo, S., Harrison, P.G., Marin, A.: A unifying approach to product-forms in networks with finite capacity constraints. In: Misra, V., Barford, P., Squillante, M.S. (eds.) Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 25–36. New York, NY, USA (14–18 June 2010)
Balsamo, S., Harrison, P.G., Marin, A.: Methodological construction of product-form stochastic Petri-nets for performance evaluation. J. Syst. Softw. 85(7), 1520–1539 (2012)
Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2), 248–260 (1975)
Buchholz, P.: Exact and ordinary lumpability in finite Markov chains. J. Appl. Probab. 31, 59–75 (1994)
Dovier, A., Piazza, C., Policriti, A.: An efficient algorithm for computing bisimulation equivalence. Theoret. Comput. Sci. 311(1–3), 221–256 (2004)
Gates, D.J., Westcott, M.: Kinetics of polymer crystallization. Discrete and continuum models. Proc. R. Soc. Lond. 416, 443–461 (1988)
Gelenbe, E.: Random neural networks with negative and positive signals and product form solution. Neural Comput. 1(4), 502–510 (1989)
Gelenbe, E.: Product form networks with negative and positive customers. J. Appl. Prob. 28(3), 656–663 (1991)
Gelenbe, E., Mitrani, I.: Analysis and Synthesis of Computer Systems, 2nd edn. Imperial College Press, London (2010)
Gelenbe, E., Schassberger, M.: Stability of product form G-networks. Prob. Eng. Inf. Sci. 6, 271–276 (1992)
Gilmore, S., Hillston, J., Ribaudo, M.: An efficient algorithm for aggregating PEPA models. IEEE Trans. Softw. Eng. 27(5), 449–464 (2001)
Harrison, P.G.: Turning back time in Markovian process algebra. Theoret. Comput. Sci. 290(3), 1947–1986 (2003)
Harrison, P.G., Marin, A.: Product-forms in multi-way synchronizations. Comput. J. 57(11), 1693–1710 (2014)
Hermanns, H.: Interactive Markov Chains and the Quest for Quantified Quality, LNCS, vol. 2428. Springer, Berlin (2002)
Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge Press, Cambridge (1996)
Hillston, J., Thomas, N.: A syntactical analysis of reversible PEPA models. In: Proceedings of of 6th International Workshop on Process Algebra and Performance Modelling, pp. 37–49 (1998)
Kelly, F.: Reversibility and Stochastic Networks. Wiley, New York (1979)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Springer, New York (1976)
King, W.F.: Analysis of paging algorithms. In: Proceedings of IFIP Congress (1971)
Lazowska, E.D., Zahorjan, J.L., Graham, G.S., Sevcick, K.C.: Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice Hall, Englewood Cliffs (1984)
Mairesse, J., Nguyen, H.T.: Deficiency zero Petri nets and product form. In: Proceedings of the 30th International Conference on Application and Theory of Petri Nets, PETRI NETS ’09, pp. 103–122. Springer-Verlag, Paris, France (2009)
Marin, A., Rossi, S.: Autoreversibility: exploiting symmetries in Markov chains. In: Proceedings of the IEEE 21st International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems MASCOTS, pp. 151–160. IEEE Computer Society (2013)
Marin, A., Rossi, S.: On discrete time reversibility modulo state renaming and its applications. In: Proceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS, pp. 1–8 (2014)
Marin, A., Rossi, S.: On the relations between lumpability and reversibility. In: Proc. of the IEEE 22nd International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems, MASCOTS, pp. 427–432. IEEE Computer Society (2014)
Marin, A., Rossi, S.: Lumping-based equivalences in Markovian automata and applications to product-form analyses. In: Proceedings of the 12th International Conference on Quantitative Evaluation of Systems, QEST, LNCS, vol. 9259, pp. 160–175. Springer (2015)
Marsan, M.A., Conte, G., Balbo, G.: A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Trans. Comput. Syst. 2(2), 93–122 (1984)
Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)
Neuts, M.F.: Structured Stochastic Matrices of M/G/1 Type and Their Application. Marcel Dekker, New York (1989)
Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987)
Schweitzer, P.: Aggregation methods for large Markov chains. In: Proceedings of the International Workshop on Computer Performance and Reliability, pp. 275–286. North Holland (1984)
Sereno, M.: Towards a product form solution for stochastic process algebras. Comput. J. 38(7), 622–632 (1995)
Sumita, U., Rieders, M.: Lumpability and time reversibility in the aggregation–disaggregation method for large Markov chains. Stoch. Models 5(1), 63–81 (1989)
Takahashi, Y.: A lumping method for numerical calculations of statioanry distributions of Markov chains. In: Technical Report B-18, Department of Information Sciences, Tokyo Institute of Technology (1975)
Whittle, P.: Systems in stochastic equilibrium. Wiley, New York (1986)
Yap, V.: Similar states in continuous-time Markov chains. J. Appl. Probab. 46, 497–506 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Marin, A., Rossi, S. On the relations between Markov chain lumpability and reversibility. Acta Informatica 54, 447–485 (2017). https://doi.org/10.1007/s00236-016-0266-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-016-0266-1