The theory of time-reversibility has been widely used to derive the expressions of the invariant measures and, consequently, of the equilibrium distributions for a large class of Markov chains which found applications in optimisation problems, computer science, physics, and bioinformatics. One of the key-properties of reversible models is that the truncation of a reversible Markov chain is still reversible. In this work we consider a more general notion of reversibility, i.e., the reversibility modulo state renaming, called rho-reversibility, and show that some of the properties of reversible chains cannot be straightforwardly extended to rho-reversible ones. Among these properties, we show that in general the truncation of the state space of a rho-reversible chain is not rho-reversible. Hence, we derive further conditions that allow the formulation of the well-known properties of reversible chains for rho-reversible Markov chains. Finally, we study the properties of the state aggregation in rho-reversible chains and prove that there always exists a state aggregation that associates a rho-reversible process with a reversible one.

The theory of time-reversibility has been widely used to derive the expressions of the invariant measures and, consequently, of the equilibrium distributions for a large class of Markov chains which found applications in optimisation problems, computer science, physics, and bioinformatics. One of the key-properties of reversible models is that the truncation of a reversible Markov chain is still reversible. In this work we consider a more general notion of reversibility, i.e., the reversibility modulo state renaming, called ρ-reversibility, and show that some of the properties of reversible chains cannot be straightforwardly extended to ρ-reversible ones. Among these properties, we show that in general the truncation of the state space of a ρ-reversible chain is not ρ-reversible. Hence, we derive further conditions that allow the formulation of the well-known properties of reversible chains for ρ-reversible Markov chains. Finally, we study the properties of the state aggregation in ρ-reversible chains and prove that there always exists a state aggregation that associates a ρ-reversible process with a reversible one.

Aggregation and Truncation of Reversible Markov Chains Modulo State Renaming

MARIN, Andrea;ROSSI, Sabina
2017-01-01

Abstract

The theory of time-reversibility has been widely used to derive the expressions of the invariant measures and, consequently, of the equilibrium distributions for a large class of Markov chains which found applications in optimisation problems, computer science, physics, and bioinformatics. One of the key-properties of reversible models is that the truncation of a reversible Markov chain is still reversible. In this work we consider a more general notion of reversibility, i.e., the reversibility modulo state renaming, called ρ-reversibility, and show that some of the properties of reversible chains cannot be straightforwardly extended to ρ-reversible ones. Among these properties, we show that in general the truncation of the state space of a ρ-reversible chain is not ρ-reversible. Hence, we derive further conditions that allow the formulation of the well-known properties of reversible chains for ρ-reversible Markov chains. Finally, we study the properties of the state aggregation in ρ-reversible chains and prove that there always exists a state aggregation that associates a ρ-reversible process with a reversible one.
2017
Analytical and Stochastic Modelling Techniques and Applications - 24th International Conference, ASMTA 2017, Newcastle-upon-Tyne, UK, July 10-11, 2017, Proceedings.
File in questo prodotto:
File Dimensione Formato  
asmta17.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 368.07 kB
Formato Adobe PDF
368.07 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: https://hdl.handle.net/10278/3692879
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact