Sequential importance sampling for multiway tables

Abstract

We describe an algorithm for the sequential sampling of entries in multiway contingency tables with given constraints. The algorithm can be used for computations in exact conditional inference. To justify the algorithm, a theory relates sampling values at each step to properties of the associated toric ideal using computational commutative algebra. In particular, the property of interval cell counts at each step is related to exponents on lead indeterminates of a lexicographic Gröbner basis. Also, the approximation of integer programming by linear programming for sampling is related to initial terms of a toric ideal. We apply the algorithm to examples of contingency tables which appear in the social and medical sciences. The numerical results demonstrate that the theory is applicable and that the algorithm performs well.

Published at http://dx.doi.org/10.1214/009053605000000822 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (16)

• Maximum likelihood estimation in log-linear models
• Connecting the latent multinomial
• Multigraded Commutative Algebra of Graph Decompositions
• fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences
• Positive margins and primary decomposition
• Gröbner bases for staged trees
• Toric fiber products versus Segre products
• Unimodular hierarchical models and their Graver bases
• Markov chain Monte Carlo methods for the Box-Behnken designs and centrally symmetric configurations
• Semigroups and sequential importance sampling for multiway tables
• Markov bases and subbases for bounded contingency tables
• Normal Toric Ideals of Low Codimension
• One Step to Efficient Synthetic Data
• Semigroups and sequential importance sampling for multiway tables and beyond
• Learning to sample fibers for goodness-of-fit testing
• The generating function of the polytope of transport matrices $U(r,c)$ as a positive semidefinite kernel of the marginals $r$ and $c$