×

What do we know about the Metropolis algorithm? (English) Zbl 0920.68054

Summary: The Metropolis algorithm is a widely used procedure for sampling from a specified distribution on a large finite set. We survey what is rigorously known about running times. This includes work from statistical physics, computer science, probability, and statistics. Some new results are given as an illustration of the geometric theory of Markov chains.
\(\copyright\) Academic Press.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Belsley, E., Rates of Convergence of Markov Chains Related to Association Schemes. Rates of Convergence of Markov Chains Related to Association Schemes, Ph.D. dissertation (1993), Harvard UniversityDepartment of Mathematics
[2] Chung, F., Spectral Graph Theory (1996), Am. Math. Soc: Am. Math. Soc Providence
[3] Chung, F.; Yau, S. T., Eigenvalues of graphs and Sobolev inequalities, Combin. Probab. Comput., 4, 11-25 (1995) · Zbl 0843.05073
[4] Critchlow, D., Metric Methods for Analyzing Partially Ranked Data. Metric Methods for Analyzing Partially Ranked Data, Springer Lecture Notes in Statistics, B4 (1985), Springer-Verlag: Springer-Verlag Berlin · Zbl 0589.62041
[5] Deuschel, J. D.; Mazza, C., \(L^2\), Ann. Appl. Prob., 4, 1012-1056 (1994) · Zbl 0819.60063
[6] Diaconis, P., Group Representations in Probability and Statistics (1988), Institute of Mathematical Statistics: Institute of Mathematical Statistics Hayward · Zbl 0695.60012
[7] Diaconis, P.; Hanlon, P., Eigenanalysis for some examples of the Metropolis algorithm, Contemp. Math., 138, 99-117 (1992) · Zbl 0789.05091
[8] Diaconis, P.; Saloff-Coste, L., Comparison techniques for reversible Markov chains, Ann. Appl. Probab., 3, 696-730 (1993) · Zbl 0799.60058
[9] Diaconis, P.; Saloff-Coste, L., Nash inequalities for finite Markov chains, J. Theor. Probab., 9, 459-510 (1996) · Zbl 0870.60064
[10] Diaconis, P.; Saloff-Coste, L., Logarithmic Sobolev inequalities and finite Markov chains, Ann. Appl. Probab., 6, 695-750 (1996) · Zbl 0867.60043
[11] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues for Markov chains, Ann. Appl. Probab., 1, 36-61 (1991) · Zbl 0731.60061
[12] Dyer, M.; Frieze, A.; Kannan, R., A random polynomial time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach., 38, 1-17 (1991) · Zbl 0799.68107
[13] Fill, J., Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab., 1, 62-87 (1991) · Zbl 0726.60069
[14] Fligner, M.; Verducci, J., Probability Models and Statistical Analysis for Ranking Data. Probability Models and Statistical Analysis for Ranking Data, Springer Lecture Notes in Statistics, 80 (1993), Springer-Verlag: Springer-Verlag New York
[15] Frieze, A.; Kannan, R.; Polson, N., Sampling from log concave distributions, Ann. Appl. Probab., 4, 812-837 (1994) · Zbl 0813.60060
[16] Frigessi, A.; Hwang, C.; Sheu, S.; Di Stefano, P., Convergence rates of the Gibb sampler, the Metropolis algorithm and other single-site updating dynamics, Jour. Roy. Stat. Soc. B, 55, 205-219 (1993) · Zbl 0781.60039
[17] Frigessi, A.; Martinelli, F.; Stander, J., Computational complexity of Markov chain Monte Carlo methods, technical report (1993)
[18] Gilks, W.; Best, W.; Tan, K., Adapted rejection Metropolis sampling within Gibbs sampling, Jour. Roy. Stat. Soc. C, 44, 455-472 (1995) · Zbl 0893.62110
[19] Gross, L., Logarithmic Sobolev inequalities and contractivity properties of semigroups, Lecture Notes in Mathematics, 1563 (1993), Springer-Verlag: Springer-Verlag New York/Berlin, p. 54-82 · Zbl 0812.47037
[20] Hastings, W., Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 97-109 (1970) · Zbl 0219.65008
[21] Ingrassia, S., On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds, Ann. App. Probab., 4, 347-389 (1994) · Zbl 0802.60061
[22] Jerrum, M.; Sinclair, A., Approximating the permanent, SIAM J. Comput., 18, 19-78 (1989)
[23] Jerrum, M.; Sinclair, A., Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput., 82, 93-133 (1989) · Zbl 0668.05060
[24] Jerrum, M., Large cliques elude the Metropolis process, Random Struct. Algorithms, 3, 347-359 (1992) · Zbl 0754.60018
[25] Kannan, R., Markov chains and polynomial time algorithms, Proc. 35th FOCS (1994), IEEE: IEEE Los Alamos, p. 656-671
[26] Karlin, S.; Taylor, H., A First Course in Stochastic Processes (1975), Academic Press: Academic Press New York
[27] Lawler, G.; Sokal, A., Bounds on the \(L^2\), Trans. Amer. Math. Soc., 309, 557-580 (1988) · Zbl 0716.60073
[28] Liu, J., Metropolized independent sampling and comparisons to rejection sampling and importance sampling, Statist. and Comput., 6, 113-119 (1995)
[29] Lovász, L.; Simonovits, M., Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms, 4, 359-412 (1993) · Zbl 0788.60087
[30] Martinelli, F., On the two dimensional dynamical Ising Model in the phase coexistence region, J. Statist. Phys., 76, 1179-1246 (1994) · Zbl 0839.60087
[31] Martinelli, F.; Olivieri, E.; Schonmann, R., For 2D lattice spin systems, weak mixing implies strong mixing, Commun. Math. Phys., 165, 33-47 (1994) · Zbl 0811.60097
[32] McCoy, B.; Wu, T., The Two-Dimensional Ising Model (1973), Harvard University Press: Harvard University Press Cambridge · Zbl 1094.82500
[33] Mengersen, K.; Tweedie, R., Rates of convergence of the Hastings and Metropolis algorithms, Ann. Statist., 24, 101-121 (1996) · Zbl 0854.60065
[34] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[35] Meyn, S.; Tweedie, R., Computable bounds for geometric convergence rates of Markov chains, Ann. Appl. Probab., 4, 981-1011 (1994) · Zbl 0812.60059
[36] Peskun, P., Optimum Monte Carlo sampling using Markov chains, Biometrika, 60, 607-612 (1973) · Zbl 0271.62041
[37] Rosenthal, J., Minorization conditions and convergence rates for Markov chain Monte Carlo, J. Am. Statist. Assoc., 90, 558-566 (1995) · Zbl 0824.60077
[38] Ross, K.; Xu, D., Hypergroup deformations and Markov chains, J. Theor. Probab., 7, 813-830 (1994) · Zbl 0807.60011
[39] Schonmann, R., Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region, Commun. Math. Phys., 161, 1-49 (1994) · Zbl 0796.60103
[40] Schonmann, R., Theorems and conjectures and the droplet-driven relaxation of stochastic Ising models, Probability and Phase Transition, Proceedings of the Nato Advanced Study Institute on Probability Theory of Spatial Disorder and Phase Transition, at the University of Cambridge, July 1993 (1995), p. 265-301 · Zbl 0835.60085
[41] Silver, J., Rates of Convergence for the Metropolis Algorithm and Its Variations. Rates of Convergence for the Metropolis Algorithm and Its Variations, Ph.D. dissertation (1995), Harvard UniversityDepartment of Mathematics
[42] Simon, B., The Statistical Mechanics of Lattice Gases, I (1993), Princeton University Press: Princeton University Press Princeton · Zbl 0804.60093
[43] Sinclair, A., Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Prob. Comput., 1, 351-370 (1992) · Zbl 0801.90039
[44] Sinclair, A., Algorithms for Random Generation and Counting: A Markov Chain Approach (1993), Birkhauser: Birkhauser Boston · Zbl 0780.68096
[46] Stroock, D.; Zegarlinski, B., The logarithmic Sobolev inequality for spin system on a lattice, Comm. Math. Physics, 149, 175-194 (1992) · Zbl 0758.60070
[47] Thomas, L., Bound on the mass gap for finite volume stochastic Ising models at low temperatures, Comm. Math. Physics, 126, 1-11 (1989) · Zbl 0679.60102
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.