Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains. (English) Zbl 1348.60107
Summary: We assume that the transition matrix of a Markov chain depends on a parameter \(\varepsilon\), and converges as \(\varepsilon \to 0\). The chain is irreducible for \(\varepsilon > 0\) but may have several essential communicating classes when \(\varepsilon = 0\). This leads to metastable behavior, possibly on multiple time scales. For each of the relevant time scales, we derive two effective chains. The first one describes the (possibly irreversible) metastable dynamics, while the second one is reversible and describes metastable escape probabilities. Closed probabilistic expressions are given for the asymptotic transition probabilities of these chains. As a consequence, we obtain efficient algorithms for computing the committor function and the limiting stationary distribution.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60F05 | Central limit and other weak theorems |
| 60J22 | Computational methods in Markov chains |
| 65C40 | Numerical analysis or methods applied to Markov chains |
Keywords:
non-reversible Markov chains; escape times; asymptotics; limiting stationary distribution; algorithmReferences:
| [1] | D. Aldous, J.A. Fill, Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/ aldous/RWG/book.html. |
| [2] | Beltran, J.; Landim, C., Tunneling and metastability of continuous time Markov chains II, the nonreversible case, J. Stat. Phys., 149, 598-618, (2012) · Zbl 1260.82063 |
| [3] | Berglund, N.; Gentz, B., Noise-induced phenomena in slow-fast dynamical systems: A sample-paths approach, (2006), Springer · Zbl 1098.37049 |
| [4] | Berglund, N.; Gentz, B.; Kuehn, C., From random poincare maps to stochastic mixed-mode-oscillation patterns, J. Dynam. Differential Equations, 27, 83-136, (2015) · Zbl 1348.37087 |
| [5] | Bovier, A., Metastability, (Kotecky, R., Methods of Contemporary Mathematical Statistical Physics, Lecture Notes in Mathematics, vol. 2009, (2006), Springer) · Zbl 1180.82008 |
| [6] | Bovier, A.; Eckhoff, M.; Gayrard, V.; Klein, M., Metastability and low-lying spectra in reversible Markov chains, Comm. Math. Phys., 228, 219-255, (2002) · Zbl 1010.60088 |
| [7] | Bovier, A.; Eckhoff, M.; Gayrard, V.; Klein, M., Metastability in reversible diffusion processes 1. sharp asymptotics for capacities and exit times, J. Eur. Math. Soc. (JEMS), 6, 399-424, (2004) · Zbl 1076.82045 |
| [8] | Bovier, A.; Gayrard, V.; Klein, M., Metastability in reversible diffusion processes 2. precise asymptotics for small eigenvalues, J. Eur. Math. Soc. (JEMS), 7, 69-99, (2005) · Zbl 1105.82025 |
| [9] | Cameron, M., Computing the asymptotic spectrum for networks representing energy landscapes using the minimal spanning tree, Netw. Heterog. Media, 9, 383-416, (2014) · Zbl 1302.65037 |
| [10] | Cameron, M.; Vanden-Eijnden, E., Flows in complex networks: theory, algorithms, and application to lennard-Jones cluster rearrangement, J. Stat. Phys., 156, 427-454, (2014) · Zbl 1301.82031 |
| [11] | De Sterck, H.; Miller, K.; Treister, E.; Yavneh, I., Fast multilevel methods for Markov chains, Numer. Linear Algebra Appl., 18, 961-980, (2011) · Zbl 1265.65009 |
| [12] | Ellison, G., Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution, Rev. Econ. Stud., 67, 17-45, (2000) · Zbl 0956.91027 |
| [13] | Eyring, H., The activated complex in chemical reactions, J. Chem. Phys., 3, 107-115, (1935) |
| [14] | Freidlin, M. I.; Wentzell, A. D., Random perturbations of dynamical systems, (1998), Springer-Verlag New York · Zbl 0922.60006 |
| [15] | Gaudilliere, A.; Landim, C., A Dirichlet principle for non reversible Markov chains and some recurrence theorems, Probab. Theory Related Fields, 158, 55-89, (2014) · Zbl 1295.60087 |
| [16] | Kramers, H. A., Brownian motion in a field of force and the diffusion model of chemical reactions, Physica, 7, 284-304, (1940) · Zbl 0061.46405 |
| [17] | Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov chains and mixing times, (2008), AMS Publishing |
| [18] | Louchard, G.; Latouche, G., Geometric bounds on iterative approximations for nearly completely decomposable Markov chains, J. Appl. Probab., 27, 521-529, (1990) · Zbl 0721.60069 |
| [19] | Meyer, C. D., Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM Rev., 31, 2, 240-272, (1989) · Zbl 0685.65129 |
| [20] | A. Milias-Argeitis, J. Lygeros, Efficient stochastic simulation of metastable Markov chains, in: 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) Orlando, FL, USA, December 12-15, 2011. |
| [21] | Olivieri, E.; Scoppola, E., Markov chains with exponentially small transition probabilities: first exit problem from a general domain I. the reversible case, J. Stat. Phys., 79, 613-647, (1995) · Zbl 1081.60541 |
| [22] | Olivieri, E.; Scoppola, E., Markov chains with exponentially small transition probabilities: first exit problem from a general domain II. the general case, J. Stat. Phys., 84, 987-1041, (1996) · Zbl 1081.60542 |
| [23] | Olivieri, E.; Vares, M. E., Large deviations and metastability, (2005), Cambridge University |
| [24] | Simon, H. A.; Ando, A., Aggregation of variables in dynamic systems, Econometrica, 111-138, (1961) · Zbl 0121.15103 |
| [25] | Tifenbach, R. M., A combinatorial approach to nearly uncoupled Markov chains 1: reversible Markov chains, Electron. Trans. Numer. Anal., 40, 120-147, (2013) · Zbl 1288.65011 |
| [26] | Vanden-Eijnden, E., Transition path theory, (Ferrario, M.; Ciccotti, G.; Binder, K., Computer Simulations in Condensed Matter: From Materials to Chemical Biology, (2006), Springer), 439-478 |
| [27] | Wicks, J. R.; Greenwald, A., An algorithm for computing stochastically stable distributions with applications to multiagent learning in repeated games, (Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, 2005, (2005), AUAI Press) |
| [28] | J.R. Wicks, A. Greenwald, A quotient construction on Markov chains with applications to the theory of generalized simulated annealing, in: International Symposium on Artificial Intelligence and Mathematics (ISAIM 2006), Fort Lauderdale, Florida, USA. · Zbl 1136.68340 |
| [29] | Young, H. P., The evolution of conventions, Econometrica, 61, 57-84, (1993) · Zbl 0773.90101 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
