Utilizing hitting times for finding metastable sets in non-reversible Markov chains

Please always quote using this URN: urn:nbn:de:0297-zib-51209
  • 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.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Marco Sarich, Christof Schütte
Document Type:ZIB-Report
Tag:directed networks; hitting times; metastability; non-reversible Markov chain; random walk
MSC-Classification:37-XX DYNAMICAL SYSTEMS AND ERGODIC THEORY [See also 26A18, 28Dxx, 34Cxx, 34Dxx, 35Bxx, 46Lxx, 58Jxx, 70-XX] / 37Mxx Approximation methods and numerical treatment of dynamical systems [See also 65Pxx] / 37M99 None of the above, but in this section
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Jxx Markov processes / 60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) [See also 90B30, 91D10, 91D35, 91E40]
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Jxx Markov processes / 60J22 Computational methods in Markov chains [See also 65C40]
Date of first Publication:2014/08/13
Series (Serial Number):ZIB-Report (14-32)
ISSN:1438-0064
Published in:To appear in: Journal of Comput. Dynamics

$Rev: 13581 $