The Library
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
Tools
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. doi:10.1137/S0097539703434243 ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/S0097539703434243
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 [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 | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2006 | ||||
Dates: |
|
||||
Volume: | 36 | ||||
Number: | 1 | ||||
Number of Pages: | 32 | ||||
Page Range: | pp. 247-278 | ||||
DOI: | 10.1137/S0097539703434243 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |