A General Limitation on Monte Carlo Algorithms of Metropolis Type

Abstract

We prove that for any Monte Carlo algorithm of Metropolis type, the autocorrelation time of a suitable ``energy''-like observable is bounded below by a multiple of the corresponding ``specific heat''. This bound does not depend on whether the proposed moves are local or non-local; it depends only on the distance between the desired probability distribution $\pi$ and the probability distribution ${\pi }^{(0)}$ for which the proposal matrix satisfies detailed balance. We show, with several examples, that this result is particularly powerful when applied to non-local algorithms.

8 pages, LaTeX plus subeqnarray.sty (included at end), NYU-TH-93/07/01, IFUP-TH33/93

References in corpus (3)

• Critical Exponents of the Classical 3D Heisenberg Model: A Single-Cluster Monte Carlo Study
• Wolff-Type Embedding Algorithms for General Nonlinear $\sigma$-Models
• Finite-Size Scaling Study of the Three-Dimensional Classical Heisenberg Model

Cited by in corpus (6)

• MCMC using Hamiltonian dynamics
• Monte Carlo methods in statistical physics: Mathematical foundations and strategies
• Bilocal Dynamics for Self-Avoiding Walks
• The 3-State Potts Antiferromagnet on the Hexagonal Lattice
• Exact sampling of corrugated surfaces
• Non-reversibly updating a uniform [0,1] value for Metropolis accept/reject decisions