Simulating Markov Random Fields With a Conclique-Based Gibbs Sampler

Abstract

For spatial and network data, we consider models formed from a Markov random field (MRF) structure and the specification of a conditional distribution for each observation. Fast simulation from such MRF models is often an important consideration, particularly when repeated generation of large numbers of datasets is required. However, a standard Gibbs strategy for simulating from MRF models involves single-site updates, performed with the conditional univariate distribution of each observation in a sequential manner, whereby a complete Gibbs iteration may become computationally involved even for moderate samples. As an alternative, we describe a general way to simulate from MRF models using Gibbs sampling with “concliques” (i.e., groups of nonneighboring observations). Compared to standard Gibbs sampling, this simulation scheme can be much faster by reducing Gibbs steps and independently updating all observations per conclique at once. The speed improvement depends on the number of concliques relative to the sample size for simulation, and order-of-magnitude speed increases are possible with many MRF models (e.g., having appropriately bounded neighborhoods). We detail the simulation method, establish its validity, and assess its computational performance through numerical studies, where speed advantages are shown for several spatial and network examples. Supplementary materials for this article are available online.

Keywords:

• Gibbs sampling
• Markov chain Monte Carlo
• Markov random fields
• Network resampling
• Spatial resampling

Supplementary Materials

Appendices:Includes additional versions of the conclique Gibbs sampler, proofs of ergodicity results, a construction of concliques for graphs with incident neighborhoods, and a spatial bootstrap example. (Zip file)

Code:All code necessary to reproduce the results in this article. (Zip file)

Data:An archive containing the data from Section 5.2. (Zip file)

Acknowledgments

The authors are grateful to two reviewers, an associate editor, and the editor (Prof. Tyler McCormick) for thoughtful comments and suggestions that greatly improved the article.

Additional information

Funding

Research partially supported by NSF DMS-1310068, DMS-1613192, and DMS-1406747.