Improved bounds for sampling contingency tables
Author:
- 25 July 2002
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (2) , 135-146
Abstract
We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums ri and the column sums cj satisfy ri = Ω(n3/2m log m), and cj = Ω(m3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002Keywords
This publication has 10 references indexed in Scilit:
- Polynomial-time counting and sampling of two-rowed contingency tablesTheoretical Computer Science, 2000
- Hit-and-run mixes fastMathematical Programming, 1999
- Faster mixing via average conductance1999
- Random walks and anO*(n5) volume algorithm for convex bodiesRandom Structures & Algorithms, 1997
- Sampling contingency tablesRandom Structures & Algorithms, 1997
- Sampling lattice points1997
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Testing for Independence in a Two-Way Table: New Interpretations of the Chi-Square StatisticThe Annals of Statistics, 1985
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963