A Bisimulation-Based Foundation for Scale Reductions of Continuous-Time Markov Chains

Abstract

<p>In this paper, the scale reduction problem of continuous-time Markov chains (CT-MCs) and continuous-time controlled Markov chains (CT-CMCs) are disserted both from the bisimulation perspective. Based on the features of bisimulation, the reachability, macro-controllability, controllability, and stabilizability of CT-MCs and CT-CMCs, particularly, the large-scale ones, are addressed over the corresponding reduced chains. The bisimulation relations are defined for both CT-MCs and CT-CMCs to establish the equivalence between the original networks and their condensed networks. A computable algorithm is developed to compute the reachability-based maximal bisimulation relation for CMCs, resulting in the smallest bisimulating CMCs. Notably, one advantage of our techniques lies in their efficiency in implementing the existing analysis and control results on MCs and CMCs in a lower amount of time, with wide applications to logical networks, finite-field networks, finite automata, and Petri nets. Compared to their discrete-time counterparts, CT-MCs and CT-CMCs inherit a simplified essential network topology in the discrete-time structures while providing a quantitative description of transient functional kinetics on the micro-time scale level. Besides, all the developed theoretical results for CT-MCs and CT-CMCs are operated based on the transition rate matrices of chains rather than transition probability matrices used in the traditional methods. Finally, the derived theoretical results are validated by investigating the p53-Mdm2 signaling network and a relevant case-study involving a set of randomly generated CT-CMCs.<br></p>