Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows

Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell Martin

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291-310] have recently given a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which employs Markov chain methods indirectly. They leave open the question as to whether a natural Markov chain on such tables mixes rapidly. Here we show that the "2 x 2 heat-bath" Markov chain is rapidly mixing. We prove this by considering first a heat-bath chain operating on a larger window. Using techniques developed by Morris [Random Walks in Convex Sets, Ph. D. thesis, Department of Statistics, University of California, Berkeley, CA, 2000] and Morris and Sinclair [SIAM J. Comput., 34 (2004), pp. 195-226] for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste [Ann. Appl. Probab., 3 (1993), pp. 696-730] to show that the 2 x 2 chain is also rapidly mixing.
Original languageEnglish
Pages (from-to)247-278
Number of pages32
JournalSIAM Journal on Computing
Volume36
Issue number1
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows'. Together they form a unique fingerprint.

Cite this