Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
UNSPECIFIED. (2006) Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. SIAM JOURNAL ON COMPUTING, 36 (1). pp. 247-278. ISSN 0097-5397Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/S0097539703434243
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.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Journal or Publication Title:||SIAM JOURNAL ON COMPUTING|
|Number of Pages:||32|
|Page Range:||pp. 247-278|
Actions (login required)