Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows

Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 [3] have recently given a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which only employs Markov chain methods indirectly. But they leave open the question as to whether a natural Markov chain on such tables mixes rapidly. Here we answer this question in the affirmative, and hence provide a very different proof of the main result of [3]. We show that the "2 × 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 and Sinclair [20] (see also Morris [19]) for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste [8] to show that the 2 × 2 chain is rapidly mixing. As part of our analysis, we give the first proof that the 2 × 2 chain mixes in time polynomial in the input size when both the number of rows and the number of columns is constant.
Original languageEnglish
Title of host publicationProceedings of the 43rd Symposium on Foundations of Computer Science
Place of PublicationWashington, DC, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Print)0-7695-1822-2
Publication statusPublished - 2002

Publication series

NameFOCS '02
PublisherIEEE Computer Society


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