Sequential importance sampling for multiway tables

Yuguo Chen, Ian H. Dinwoodie, Seth Sullivant

Research output: Contribution to journalArticlepeer-review


We describe an algorithm for the sequential sampling of entries in multi-way 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.

Original languageEnglish (US)
Pages (from-to)523-545
Number of pages23
JournalAnnals of Statistics
Issue number1
StatePublished - Feb 2006


  • Conditional inference
  • Contingency table
  • Exact test
  • Monte Carlo
  • Sequential importance sampling
  • Toric ideal

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Sequential importance sampling for multiway tables'. Together they form a unique fingerprint.

Cite this