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-5397

Full text not available from this repository.

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
Date:	2006
Volume:	36
Number:	1
Number of Pages:	32
Page Range:	pp. 247-278
Identification Number:	10.1137/S0097539703434243
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/33391

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item