60J22 Computational methods in Markov chains [See also 65C40]
Refine
Document Type
- ZIB-Report (2) (remove)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- metastability (2)
- $n$-pentane molecule (1)
- almost invariant sets (1)
- bridge sampling (1)
- directed networks (1)
- hierarchical annealing (1)
- hitting times (1)
- hybrid Monte Carlo (1)
- non-reversible Markov chain (1)
- random walk (1)
Institute
- Numerical Mathematics (1)
- ZIB Allgemein (1)
Techniques for finding metastable or almost invariant sets have been investigated, e.g., for deterministic dynamical systems in set-oriented numerics, for stochastic processes in molecular dynamics, and for random walks on complex networks. Most prominent algorithms are based on spectral apporaches and identify metastable sets via the doimant eigenvalues of the transfer operator associated with the dynamical system under consideration. These algorithms require the dominant eigenvalues to be real-valued. However, for many types of dynamics, e.g. for non-reversible Markov chains, this condition is not met. In this paper we utilize the hitting time apporach to metastable sets and demonstrate how the wellknown statements about optimal metastable decompositions of reversible chains can be reformulated for non-reversible chains if one switches from a spectral approach to an exit time approach. The performance of the resulting algorithm is illustrated by numerical experiments on random walks on complex networks.
Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.