# Convergence tests in Markov Chain Monte Carlo

For a relatively simple Markov chain Monte Carlo process, such as using Metropolis to find calculate thermal averages for an Ising model, how is it possible to determine whether quantities have converged?

If one knows the autocorrelation time, this seems relatively simple. You just run it for a sufficiently high multiple of this time and Bob's your uncle.

If you don't know the autocorrelation time, it would seem more complex. No matter how hard you try to ensure that your averages have converged, there's always the possibility that it is stuck in a local minima. This is especially troublesome if the autocorrelation time scales polynomially or even exponentially with the system size.

So how can you ensure that the quantities really have converged? What convergence tests are not fooled by local minima? I read here recently about the method of logarithmic binning. Could that do the job?

-
I think there are almost by definition no such tests. Suppose you use a 'bad' (non-cluster) algorithm on the Ising model in the broken phase, then indeed you can simulate for days getting wrong estimates for your observables. However, your data will be perfectly consistent and no data analysis/binning/whatever will tell you that you're wrong, unless you extend the runtime of your simulation. –  Vibert Jun 8 at 20:49
Yes, it's a difficult problem. Nevertheless, in simple enough situations, such as the one mentioned here, it is possible to implement a perfect simulation algorithm, i.e., one that returns (after a random, but almost surely finite, time) a configuration sampled exactly from the Gibbs measure. Relevant keywords are: Propp-Wilson algorithm and coupling from the past. –  Yvan Velenik Jun 8 at 21:53

## migrated from physics.stackexchange.comJun 8 at 22:09

This question came from our site for active researchers, academics and students of physics.

It's very hard to prove convergence for an ensemble in statistical mechanics, for exactly the reasons you've suggested—you may be stuck moving around a local minimum, instead of sampling the complete phase space. About the best that you can do is to demonstrate likely convergence of your simulation.

However, you can do calculations to demonstrate autocorrelation of various properties. For instance, you can measure the autocorrelation of the energy function: $\left<E(t)E(t + \delta t) \right>$. Alternatively, you can use the multiscale error correlation method of Flyvbjerg and Petersen to determine when your data samples are effectively decorrelated from one another, and use that as a means of determining whether you have enough data (and to estimate the statistical error in the mean of your data samples).

-
How can such a correlation method 'likely' prove convergence? How does it know about other local minima your data are not seeing? –  Vibert Jun 10 at 13:15
For starters, if you're stuck in a deep minimum, you're unlikely to get away from it. Hence your decorrelation time, as measured by the algorithm, would be quite long, relative to the length of your simulation. That would mean you've sampled relatively few independent states, which would violate the general principles behind molecular simulations (which states that large numbers of data points, generated either by time trajectories or random sampling of phase space will generate a good estimate of the "true" observable). –  aeismail Jun 10 at 16:17