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
Commented Jun 8, 2013 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
Commented Jun 8, 2013 at 21:53

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).