sas 15(3): e2

Research Article

On Discrete Time Reversibility modulo State Renaming and its Applications

Download321 downloads
  • @ARTICLE{10.4108/icst.valuetools.2014.258200,
        author={Sabina Rossi and Andrea Marin},
        title={On Discrete Time Reversibility modulo State Renaming and its Applications},
        journal={EAI Endorsed Transactions on Self-Adaptive Systems},
        volume={1},
        number={3},
        publisher={EAI},
        journal_a={SAS},
        year={2015},
        month={2},
        keywords={discrete time markov chains, reversibility},
        doi={10.4108/icst.valuetools.2014.258200}
    }
    
  • Sabina Rossi
    Andrea Marin
    Year: 2015
    On Discrete Time Reversibility modulo State Renaming and its Applications
    SAS
    EAI
    DOI: 10.4108/icst.valuetools.2014.258200
Sabina Rossi1,*, Andrea Marin1
  • 1: Univ. Ca' Foscari of Venice
*Contact email: srossi@dais.unive.it

Abstract

Time reversibility plays an important role in the analysis of continuous and discrete time Markov chains (DTMCs). Specifically, the computation of the stationary distribution of a reversible Markov chain has been proved to be very efficient and does not require the solution of the system of global balance equations. A DTMC is reversible when the processes at forward and reversed time are probabilistically indistinguishable. In this paper we introduce the concept of ρ-reversibility, i.e., a notion of reversibility modulo a renaming of the states, and we contrast it with the previous definition of dynamic reversibility especially with respect to the assumptions on the state renaming function. We also discuss the applications of discrete time reversibility in the embedded and uniformized chains of continuous time processes.