A graph-algorithmic approach for the study of metastability in Markov chains
From MaRDI portal
Publication:2359424
Abstract: 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 prefactors) 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.
Recommendations
- Graph-combinatorial approach for large deviations of Markov chains
- Metastability for Glauber dynamics on random graphs
- scientific article; zbMATH DE number 3907513
- A Markov chain approach to randomly grown graphs
- Metastable Markov chains
- scientific article; zbMATH DE number 797405
- Metastability of Markov chains and in the Hopfield model
- scientific article; zbMATH DE number 6450685
- Constrained Markovian dynamics of random graphs
- Threshold Functions for Markov Chains: a Graph Theoretic Approach
Cites work
- Computing Freidlin's cycles for the overdamped Langevin dynamics. Application to the Lennard-Jones-38 cluster
- Computing the asymptotic spectrum for networks representing energy landscapes using the minimum spanning tree
- Deriving finite sphere packings
- Generalisation of the Eyring-Kramers transition rate formula to irreversible diffusion processes
- scientific article; zbMATH DE number 3592362 (Why is no real title available?)
- scientific article; zbMATH DE number 3002670 (Why is no real title available?)
- scientific article; zbMATH DE number 3285076 (Why is no real title available?)
- Markov Chains
- Metastability and low lying spectra in reversible Markov chains
- Metastability in reversible diffusion processes. I: Sharp asymptotics for capacities and exit times
- Metastability in reversible diffusion processes. II: Precise asymptotics for small eigenvalues
- Metastability. A potential-theoretic approach
- Metastable relaxation times and absorption probabilities for multidimensional stochastic systems
- On stochastic perturbations of dynamical systems with a ``rough symmetry. Hierarchy of Markov chains.
- Optimum branchings
- Quasi-deterministic approximation, metastability and stochastic resonance
- Random Perturbations of Dynamical Systems
- The Eyring-Kramers law for Markovian jump processes with symmetries
- Transition Path Theory for Markov Jump Processes
Cited in
(5)- Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
- scientific article; zbMATH DE number 6683512 (Why is no real title available?)
- Spectral theory for random Poincaré maps
- Flux in tilted potential systems: negative resistance and persistence
- Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems
This page was built for publication: A graph-algorithmic approach for the study of metastability in Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359424)
