Markov Bases: A 25 Year Update

Abstract

In this article, we evaluate the challenges and best practices associated with the Markov bases approach to sampling from conditional distributions. We provide insights and clarifications after 25 years of the publication of the Fundamental theorem for Markov bases by Diaconis and Sturmfels. In addition to a literature review, we prove three new results on the complexity of Markov bases in hierarchical models, relaxations of the fibers in log-linear models, and limitations of partial sets of moves in providing an irreducible Markov chain. Supplementary materials for this article are available online.

Keywords:

• Log-affine model
• Log-linear model
• Markov bases
• MCMC
• Sampling

Acknowledgments

The authors are grateful to the anonymous referees whose comments and constructive feedback contributed to the improvement of this article. We thank Persi Diaconis and Thomas Kahle for reading a preliminary version of this article and providing further references and suggestions. We also thank Steffen Lauritzen for bringing Besag’s 1989 parallel method to our attention several years ago. We are grateful to Despina Stasi for early discussions and to Miles Bakenhus for his assistance running code with the LattE interface in R.

Disclosure Statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

FAH and JDL are partially supported by NSF grant DMS-1818969. FAH is grateful for the support received through NSF TRIPODS Award no. CCF-1934568. SP is partially supported by DOE award #1010629 and the Simons Foundation Collaboration Grant for Mathematicians #854770.