@inproceedings{922eb2cf7c7a40d89d2f048a0cecb04b,

title = "Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows",

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 [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.",

author = "Mary Cryan and Dyer, {Martin E.} and Goldberg, {Leslie Ann} and Mark Jerrum and Martin, {Russell A.}",

year = "2002",

language = "English",

isbn = "0-7695-1822-2",

series = "FOCS '02",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

pages = "711--720",

booktitle = "Proceedings of the 43rd Symposium on Foundations of Computer Science",

address = "United States",

}