Sampling Algorithms for Discrete Markov Random Fields and Related Graphical Models

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.