Dynamic Markov Bases

Abstract

This article presents a computational approach for generating Markov bases for multiway contingency tables whose cell counts might be constrained by fixed marginals and by lower and upper bounds. Our framework includes tables with structural zeros as a particular case. Instead of computing the entire Markov bases in an initial step, our framework finds sets of local moves that connect each table in the reference set with a set of neighbor tables. We construct a Markov chain on the reference set of tables that requires only a set of local moves at each iteration. The union of these sets of local moves forms a dynamic Markov basis. We illustrate the practicality of our algorithms in the estimation of exact p-values for a three-way table with structural zeros and a sparse eight-way table. This article has online supplementary materials.

Key Words:

• Contingency tables
• Exact tests
• Markov chain Monte Carlo
• Structural zeros

Acknowledgments

This work was partially supported by a seed grant from the Center of Statistics and the Social Sciences, University of Washington. The author was supported in part by the National Science Foundation (DMS 1120255). The author thanks Anna Klimova for her assistance with some of the numerical results presented in the article. The author also thanks three anonymous reviewers and the AE for their helpful comments.