A Graph-Algorithmic Approach for the Study of Metastability in Markov Chains

作者：Gan Tingyue; Cameron Maria^*

来源：Journal of Nonlinear Science, 2017, 27(3): 927-972.

DOI：10.1007/s00332-016-9355-0

• Continuous-time Markov chain
• Optimal W-graphs
• Typical Transition Graphs
• Graph algorithms
• Symmetry
• Asymptotic estimates for eigenvalues
• Freidlin's cycles
• Molecular motor

Large continuous-time Markov chains with exponentially small transition rates arise in modeling complex systems in physics, chemistry, and biology. We propose a constructive graph-algorithmic approach to determine the sequence of critical timescales at which the qualitative behavior of a given Markov chain changes, and give an effective description of the dynamics on each of them. This approach is valid for both time-reversible and time-irreversible Markov processes, with or without symmetry. Central to this approach are two graph algorithms, Algorithm 1 and Algorithm 2, for obtaining the sequences of the critical timescales and the hierarchies of Typical Transition Graphs or T-graphs indicating the most likely transitions in the system without and with symmetry, respectively. The sequence of critical timescales includes the subsequence of the reciprocals of the real parts of eigenvalues. Under a certain assumption, we prove sharp asymptotic estimates for eigenvalues (including pre-factors) and show how one can extract them from the output of Algorithm 1. We discuss the relationship between Algorithms 1 and 2 and explain how one needs to interpret the output of Algorithm 1 if it is applied in the case with symmetry instead of Algorithm 2. Finally, we analyze an example motivated by R. D. Astumian's model of the dynamics of kinesin, a molecular motor, by means of Algorithm 2.

• 出版日期2017-6