A Divide-and-Conquer Algorithm for Generating Markov Bases of Multi-way Tables (2002)

Abstract:

We describe a divide-and-conquer technique for generating a Markov basis that connects all tables of counts having a fixed set of marginal totals.  This procedure us based on deposing the independence graph induced by these marginals.  We discuss the practical imports of using this method in conjunction with other algorithms for determining Markov bases.

Keywords:

Contingency tables; Decomposable graphical models; Disclosure limitation; Exact distributions; Grobner bases; Markov bases