Running Markov Chain without Markov Basis


The methodology of Markov basis initiated by Diaconis and Sturmfels (1998) stimulated active research on Markov bases for more than a decade. It also motivated improvements of algorithms for Gr\"obner basis computation for toric ideals, such as those implemented in 4ti2.

At present, however, 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 talk we introduce some alternative methods for running Markov chain instead of using a Markov basis. The first one is to use a Markov subbasis for connecting only practical fibers. The second one is to use a lattice basis which is an integer kernel of a design matrix.
We also discuss connecting tables whose cell counts are restricted to zero or one by using Graver basis.

Start Time


Building Map