标题： 无马尔可夫基的马尔可夫链运行 显示英文标题

标题： Running Markov chain without Markov basis

摘要： 由Diaconis和Sturmfels(1998)提出的马尔可夫基方法激发了超过十年的关于马尔可夫基的积极研究。 它也促进了用于环形理想Grobner基计算的算法改进，例如在4ti2中实现的那些算法。 然而目前，仅知道一些相对简单的模型的马尔可夫基的显式形式，例如列联表的可分解模型。 此外，一般的马尔可夫基计算算法即使在合理的时间内也常常无法为中等规模的模型生成马尔可夫基。 因此到目前为止，我们无法基于马尔可夫基方法对许多重要的实际问题进行精确检验。 在本文中，我们提出在马尔可夫基未知的情况下使用格基来进行精确检验。 计算格基比计算马尔可夫基要容易得多。 通过许多例子，我们展示了使用格基的方法是可行的。 我们还检查了在已知马尔可夫基的问题上，其性能与马尔可夫基相当。 显示英文摘要

摘要： The methodology of Markov basis initiated by Diaconis and Sturmfels(1998) stimulated active research on Markov bases for more than ten years. It also motivated improvements of algorithms for Grobner basis computation for toric ideals, such as those implemented in 4ti2. However at present explicit forms of Markov bases are known only for some relatively simple models, such as the decomposable models of contingency tables. Furthermore general algorithms for Markov bases computation often fail to produce Markov bases even for moderate-sized models in a practical amount of time. Hence so far we could not perform exact tests based on Markov basis methodology for many important practical problems. In this article we propose to use lattice bases for performing exact tests, in the case where Markov bases are not known. Computation of lattice bases is much easier than that of Markov bases. With many examples we show that the approach with lattice bases is practical. We also check that its performance is comparable to Markov bases for the problems where Markov bases are known.