# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
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
Full Text:
##### References:
 [1] Belsley, E.: Rates of convergence of Markov chains related to association schemes. Ph.d. dissertation (1993) [2] Chung, F.: Spectral graph theory. (1996) [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. Springer lecture notes in statistics 4 (1985) · Zbl 0589.62041 [5] Deuschel, J. D.; Mazza, C.: L2. Ann. appl. Prob. 4, 1012-1056 (1994) [6] Diaconis, P.: Group representations in probability and statistics. (1988) · 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. Springer lecture notes in statistics 80 (1993) · Zbl 0754.00011 [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) · Zbl 0887.62096 [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) · 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) · Zbl 0723.05107 [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. (1994) [26] Karlin, S.; Taylor, H.: A first course in stochastic processes. (1975) · Zbl 0315.60016 [27] Lawler, G.; Sokal, A.: Bounds on thel2. 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) · 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) [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. (1995) · Zbl 0835.60085 [41] Silver, J.: Rates of convergence for the metropolis algorithm and its variations. Ph.d. dissertation (1995) [42] Simon, B.: The statistical mechanics of lattice gases, I. (1993) · 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) · Zbl 0780.68096 [45] A. Sokal, Monte Carlo methods in statistical mechanics: Foundations and new algorithms, Cours de troisième cycle de la physique en suisse romande, Department of Physics, NYU, 1989 [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