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

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2006-01, Vol.36 (1), p.247-278
Main Authors: Cryan, Mary, Dyer, Martin, Goldberg, Leslie Ann, Jerrum, Mark, Martin, Russell
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Computer science
Contingency tables
Dynamic programming
Markov analysis
Methods
Residuals
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-5397
1095-7111
DOI:10.1137/S0097539703434243