Spectral Analysis of Markov Jump Processes with Rare Transitions: A Graph-Algorithmic Approach

Abstract

Parameter-dependent Markov jump processes with exponentially small transition rates arise in modeling complex systems in physics, chemistry, and biology. Long-term dynamics of these processes are largely governed by the spectral properties of their generators. We propose a constructive graph-algorithmic approach to computing the asymptotic estimates of eigenvalues and eigenvectors of the generator matrix. In particular, we introduce the concepts of the hierarchy of Typical Transition Graphs (T-graphs) and the associated sequence of Characteristic Timescales. The hierarchy of T-graphs can be viewed as a unication of Wentzell's hierarchy of optimal W-graphs and Friedlin's hierarchy of Markov chains. T-graphs are capable of describing typical escapes from metastable classes as well as cyclic behaviors within metastable classes, for both reversible and irreversible processes, with or without symmetry. Moreover, the hierarchy of T-graphs can be used to construct asymptotic estimates of eigenvalues and eigenvectors simultaneously. We apply the proposed approach to investigate the biased random walk of a molecular motor and conduct zero-temperature asymptotic analysis of the LJ75 network.