×

Simple conditions for metastability of continuous Markov chains. (English) Zbl 1464.60071

Summary: A family \(\{Q_{\beta}\}_{\beta\geq 0}\) of Markov chains is said to exhibit metastable mixing with \(\mathrm{modes }S_{\beta}^{(1)},\dots,S_{\beta}^{(k)}\) if its spectral gap (or some other mixing property) is very close to the worst conductance \(\min\big(\Phi_{\beta}\big(S_{\beta}^{(1)}\big),\dots, \Phi_{\beta}\big(S_{\beta}^{(k)}\big)\big)\) of its modes for all large values of \(\beta\). We give simple sufficient conditions for a family of Markov chains to exhibit metastability in this sense, and verify that these conditions hold for a prototypical Metropolis-Hastings chain targeting a mixture distribution. The existing metastability literature is large, and our present work is aimed at filling the following small gap: finding sufficient conditions for metastability that are easy to verify for typical examples from statistics using well-studied methods, while at the same time giving an asymptotically exact formula for the spectral gap (rather than a bound that can be very far from sharp). Our bounds from this paper are used in a companion paper [the authors, “ Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities?”, Preprint, arXiv:1808.03230)] to compare the mixing times of the Hamiltonian Monte Carlo algorithm and a random walk algorithm for multimodal target distributions.

MSC:

60J05 Discrete-time Markov processes on general state spaces
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beltrán, J. and Landim, C. (2015). A martingale approach to metastability. Prob. Theory Relat. Fields161, 267-307. · Zbl 1338.60194
[2] Bovier, A. and Den Hollander, F. (2006). Metastability: A Potential Theoretic Approach. Springer, New York. · Zbl 1339.60002
[3] Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis, ed. Gunning, R. C., Princeton University Press, pp. 195-199. · Zbl 0212.44903
[4] Griffeath, D. (1975). A maximal coupling for Markov chains. Z. Wahrscheinlichkeitsth.31, 95-106. · Zbl 0301.60043
[5] Jerrum, M., Son, J.-B., Tetali, P. and Vigoda, E. (2004). Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Ann. Appl. Prob.14, 1741-1765. · Zbl 1067.60065
[6] Landim, C. (2018). Metastable Markov chains. Preprint. · Zbl 1491.60131
[7] Lawler, G. F. and Sokal, A. D. (1988). Bounds on the \(L^2\) spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality. Trans. Am. Math. Soc.309, 557-580. · Zbl 0716.60073
[8] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times. American Mathematical Society, Providence, RI. · Zbl 1160.60001
[9] Lovász, J. and Vempala, S. (2006). Hit-and-run from a corner. SIAM J. Comp.35, 985-1005. · Zbl 1103.52002
[10] Madras, N. and Randall, D. (2002). Markov chain decomposition for convergence rate analysis. Ann. Appl. Prob.12, 581-606. · Zbl 1017.60080
[11] Mangoubi, O., Pillai, N. S. and Smith, A. (2018). Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities? Preprint. arXiv:1808.03230.
[12] Mangoubi, O. and Smith, A. (2017). Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 1: Continuous dynamics. Preprint.
[13] Mangoubi, O. and Smith, A. (2017). Rapid mixing of Hamiltonian Monte Carlo on strongly log-concave distributions. Preprint. arXiv:1708.07114.
[14] Mengersen, K. L. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist.24, 101-121. · Zbl 0854.60065
[15] Meyn, S. P. and Tweedie, R. L. (1994). Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Prob.4, 981-1011. · Zbl 0812.60059
[16] Olivieri, E. and Vares, M. E. (2005). Large Deviations and Metastability. Cambridge University Press. · Zbl 1075.60002
[17] Pillai, N. S. and Smith, A. (2017). Elementary bounds on mixing times for decomposable Markov chains. Stoch. Process. Appl.127, 3068-3109. · Zbl 1395.60082
[18] Resnick, S. I. (2013). A Probability Path. Springer, New York.
[19] Roberts, G. O., Gelman, A. and Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Prob.7, 110-120. · Zbl 0876.60015
[20] Roberts, G. O. and Rosenthal, J. S. (1997). Geometric ergodicity and hybrid Markov chains. Electron. Commun. Prob.2, 13-25. · Zbl 0890.60061
[21] Rosenthal, J. S. (1995). Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Am. Statist. Assoc.90, 558-566. · Zbl 0824.60077
[22] Turchin, V. F. (1971). On the computation of multidimensional integrals by the Monte-Carlo method. Theory Prob. Appl.16, 720-724. · Zbl 0257.65030
[23] Woodard, D., Schmidler, S. and Huber, M. (2009). Sufficient conditions for torpid mixing of parallel and simulated tempering. Electron. J. Prob.14, 780-804. · Zbl 1189.65021
[24] Woodard, D. B., Schmidler, S. C. and Huber, M. (2009). Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions. Ann. Appl. Prob.19, 617-640. · Zbl 1171.65008
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.