Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields

Abstract

This paper studies the computational complexity of Markov chain Monte Carlo algorithms with finite-valued Markov random fields on a finite regular lattice as target distributions. We state conditions under which the complexity for approximate convergence is polynomial in n , the number of variables. Approximate convergence takes time O ( n log n ) as n→∞ if the target field satisfies certain spatial mixing conditions. Otherwise, if the field has a potential with finite interaction range independent of n , the complexity is exponential in n γ , with γ<1, which is still more favourable than enumerating all the states. When the interaction range grows with n , the algorithms can converge exponentially in n . Analogous results are provided for an expectation approximated by an average along the chain.