Markov Bases: A 25 Year Update

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.

本文针对基于马尔可夫基（Markov bases）从条件分布中采样的相关挑战与最佳实践展开评估。在迪亚科尼斯（Diaconis）与施图姆费尔斯（Sturmfels）发表马尔可夫基基本定理二十五载后，本文给出了相应的见解与澄清。除开展文献综述外，本文还证明了三项全新结论，分别涉及分层模型（hierarchical models）中马尔可夫基的复杂度、对数线性模型（log-linear models）中纤维（fibers）的松弛形式，以及移动子集在构造不可约马尔可夫链（irreducible Markov chain）时的局限性。本文配套补充材料可在线获取。