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

摘要

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.