Tuesday, October 16th @ 11:00-12:30 PM
Asymptotic Spectral Analysis of Markov Chains with Rare Transitions: A Graph-Algorithmic Approach
Tingyue Gan, UC Berkeley
Parameter-dependent Markov chains with exponentially small transition rates arise in modeling complex systems in physics, chemistry, and biology. Such processes often manifest metastability, and the spectral properties of the generators largely govern their long-term dynamics. In this work, we propose a constructive graph-algorithmic approach to computing the asymptotic estimates of eigenvalues and eigenvectors of the generator. In particular, we introduce the concepts of the hierarchy of Typical Transition Graphs and the associated sequence of Characteristic Timescales. Typical Transition Graphs can be viewed as a unification of Wentzell’s hierarchy of optimal W-graphs and Friedlin’s hierarchy of Markov chains, and they are capable of describing typical escapes from metastable classes as well as cyclic behaviors within metastable classes, for both reversible and irreversible processes. We apply the proposed approach to conduct zero-temperature asymptotic analysis of the stochastic network representing the energy landscape of the Lennard-Jones cluster of 75 atoms.