Sampling Algorithms for Discrete Markov Random Fields and Related Graphical Models

Abstract

Discrete Markov random fields are undirected graphical models in which the nodes of a graph are discrete random variables with values usually represented by colors. Typically, graphs are taken to be square lattices, although more general graphs are also of interest. Such discrete MRFs have been studied in many disciplines. We describe the two most popular types of discrete MRFs, namely the two-state Ising model and the q-state Potts model, and variations such as the cellular automaton, the cellular Potts model, and the random cluster model, the latter of which is a continuous generalization of both the Ising and Potts models. Research interest is usually focused on providing algorithms for simulating from these models because the partition function is so computationally intractable that statistical inference for the parameters of the appropriate probability distribution becomes very complicated. Substantial improvements to the Metropolis algorithm have appeared in the form of cluster algorithms, such as the Swendsen–Wang and Wolff algorithms. We study the simulation processes of these algorithms, which update the color of a cluster of nodes at each iteration.

Keywords:

• Cellular Potts model
• Ising model
• Metropolis algorithm
• Potts model
• Swendsen–Wang algorithm
• Wolff algorithm

Acknowledgments

The author is grateful to Marc Sobel for helpful conversations, Doug Fletcher and Richard Heiberger for their assistance with the graphics, and Xu Zhang for his help with the simulations. The author is also grateful to an associate editor and an anonymous referee for their constructive and thoughtful comments and suggestions that led to a much improved version of this article.