ALCOMFT-TR-02-19

M. Cryan, M. Dyer, L. A. Goldberg, M. Jerrum and R. Martin
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
Warwick. Work package 4. May 2002.

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 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 their main result. We show that the ``2x 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 for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste to show that the 2x 2 chain is rapidly mixing. To establish this, we provide the first proof that this chain mixes in time polynomial in the input size even when both the number of rows and number of columns are constant.

Postscript file: ALCOMFT-TR-02-19.ps.gz (161 kb).