A General Limitation on Monte Carlo Algorithms of Metropolis Type

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.