Premium
An approximation algorithm for counting contingency tables
Author(s) -
Barvinok Alexander,
Luria Zur,
Samorodnitsky Alex,
Yong Alexander
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20301
Subject(s) - contingency table , mathematics , combinatorics , integer (computer science) , matrix (chemical analysis) , randomized algorithm , scaling , column (typography) , table (database) , discrete mathematics , polynomial , algorithm , time complexity , connection (principal bundle) , statistics , computer science , mathematical analysis , materials science , geometry , composite material , programming language , data mining
We present a randomized approximation algorithm for counting contingency tables , m × n non‐negative integer matrices with given row sums R = ( r 1 ,…, r m ) and column sums C = ( c 1 ,…, c n ). We define smooth margins ( R , C ) in terms of the typical table and prove that for such margins the algorithm has quasi‐polynomial N O (ln N ) complexity, where N = r 1 + … + r m = c 1 + … + c n . Various classes of margins are smooth, e.g., when m = O ( n ), n = O ( m ) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + $ {\sqrt{5}} $ )/2 ≈ 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log‐concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010