The computation of the steady-state distribution of Continuous Time Markov Chains (CTMCs) may be a computationally hard problem when the number of states is very large. In order to overcome this problem, in the literature, several solutions have been proposed such as the reduction of the state space cardinality by lumping, the factorisation based on product- form analysis and the application of the notion of reversibility. In this paper we address this problem by introducing the notion of autoreversibility which is defined as a symmetric coinductive relation which induces an equivalence relation among the chain’s states. We show that all the states belonging to the same equivalence class share the same stationary probabilities and hence the computation of the the steady-state distribution can be computationally more efficient. The definition of autoreversibility takes inspiration by the Kolmogorov’s criteria for reversible processes and hence requires to test a property on all the minimal cycles of the chain. We show that the notion of autoreversibility is different from that of reversible processes and does not correspond to other state aggregation techniques such as lumping. Finally, we discuss the applicability of our results in the case of models defined in terms of a Markovian process Algebra such as the Performance Evaluation Process Algebra.

Autoreversibility: exploiting symmetries in Markov chains

MARIN, Andrea;ROSSI, Sabina
2013

Abstract

The computation of the steady-state distribution of Continuous Time Markov Chains (CTMCs) may be a computationally hard problem when the number of states is very large. In order to overcome this problem, in the literature, several solutions have been proposed such as the reduction of the state space cardinality by lumping, the factorisation based on product- form analysis and the application of the notion of reversibility. In this paper we address this problem by introducing the notion of autoreversibility which is defined as a symmetric coinductive relation which induces an equivalence relation among the chain’s states. We show that all the states belonging to the same equivalence class share the same stationary probabilities and hence the computation of the the steady-state distribution can be computationally more efficient. The definition of autoreversibility takes inspiration by the Kolmogorov’s criteria for reversible processes and hence requires to test a property on all the minimal cycles of the chain. We show that the notion of autoreversibility is different from that of reversible processes and does not correspond to other state aggregation techniques such as lumping. Finally, we discuss the applicability of our results in the case of models defined in terms of a Markovian process Algebra such as the Performance Evaluation Process Algebra.
Proceedings of Int. Conf. MASCOTS 2013
File in questo prodotto:
File Dimensione Formato  
mascots13.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 274.96 kB
Formato Adobe PDF
274.96 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/39158
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact