Algebraic Markov Bases and MCMC for Two-Way Contingency Tables

ABSTRACT.  The Diaconis–Sturmfels algorithm is a method for sampling from conditional distributions, based on the algebraic theory of toric ideals. This algorithm is applied to categorical data analysis through the notion of Markov basis. An application of this algorithm is a non-parametric Monte Carlo approach to the goodness of fit tests for contingency tables. In this paper, we characterize or compute the Markov bases for some log-linear models for two-way contingency tables using techniques from Computational Commutative Algebra, namely Gröbner bases. This applies to a large set of cases including independence, quasi-independence, symmetry, quasi-symmetry. Three examples of quasi-symmetry and quasi-independence from Fingleton ( Models of category counts , Cambridge University Press, Cambridge, 1984) and Agresti ( An Introduction to categorical data analysis , Wiley, New York, 1996) illustrate the practical applicability and the relevance of this algebraic methodology.