Paper Info
Title
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
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 [3] 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 the main result of [3]. We show that the "2 脳 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 and Sinclair [20] (see also Morris [19]) for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste [8] to show that the 2 脳 2 chain is rapidly mixing. As part of our analysis, we give the first proof that the 2 脳 2 chain mixes in time polynomial in the input size when both the number of rows and the number of columns is constant.
Year
DOI
Venue
2006
10.1137/S0097539703434243
SIAM Journal on Computing
Keywords
DocType
Volume
ph. d,siam j. comput,multidimensional knapsack problem,rapidly mixing markov chains,heat-bath chain operating,related counting problem,natural markov chain,constant number,j. comput,convex sets,sampling contingency tables,markov chain method,markov chain
Journal
36
Issue
ISSN
ISBN
1
0097-5397
0-7695-1822-2
Citations 
PageRank 
References 
9
0.95
12
Authors
6
Name
Order
Citations
PageRank
Mary Cryan114712.69
Martin Dyer2102997.62
leslie ann goldberg31411125.20
mark jerrum42755564.62
Russell Martin518017.35
LA Goldberg6362.73