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

摘要

Large continuous-time Markov chains with exponentially small transition ratesarise in modeling complex systems in physics, chemistry and biology. We proposea constructive graph-algorithmic approach to determine the sequence of criticaltimescales at which the qualitative behavior of a given Markov chain changes,and give an effective description of the dynamics on each of them. Thisapproach is valid for both time-reversible and time-irreversible Markovprocesses, with or without symmetry. Central to this approach are two graphalgorithms, Algorithm 1 and Algorithm 2, for obtaining the sequences of thecritical timescales and the hierarchies of Typical Transition Graphs orT-graphs indicating the most likely transitions in the system {without andwith} symmetry respectively. The sequence of {critical} timescales includes thesubsequence of the reciprocals { of the real parts } of eigenvalues. Under acertain assumption, we prove sharp asymptotic estimates for eigenvalues(including prefactors) and show how one can extract them from the output ofAlgorithm 1. We discuss the relationship between Algorithms 1 and 2, andexplain how one needs to interpret the output of Algorithm 1 if it is appliedin the case with symmetry instead of Algorithm 2. Finally, we analyze anexample motivated by R. D. Astumian's model of the dynamics of kinesin, amolecular motor, by means of Algorithm 2.