An approximation algorithm for counting contingency tables

DOI10.1002/RSA.20301MaRDI QIDQ3057067zbMATH OpenOpenAlexFDO

Authors Zur Luria, Alex Samorodnitsky, Alexander Yong, Alexander Barvinok

Publication date 24 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.3948, http://hdl.handle.net/2027.42/77454

zbMATH Keywords

matrix scalingpermanent approximationrandomized algorithmssmooth margins

Mathematics Subject Classification ID

Contingency tables (62H17) Monte Carlo methods (65C05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We present a randomized approximation algorithm for counting contingency tables, mxn 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.

Recommendations

• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• Enumerating Contingency Tables via Random Permanents
• Sampling contingency tables
• Polynomial-time counting and sampling of two-rowed contingency tables
• Improved bounds for sampling contingency tables

Cites work

• A course in combinatorics.
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• A lower bound for the permanent of a doubly stochastic matrix
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Brunn--Minkowski inequalities for contingency tables and integer flows
• Counting integer flows in networks
• Enumerating Contingency Tables via Random Permanents
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• Improved bounds for sampling contingency tables
• Log-Sobolev inequalities and sampling from log-concave distributions
• New permanental upper bounds for nonnegative matrices
• On the application of symmetric Dirichlet distributions and their mixtures to contingency tables
• On the complexity of nonnegative-matrix scaling
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Sampling from log-concave distributions
• Scaling of matrices to achieve specified row and column sums
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• The asymptotic number of non-negative integer matrices with given row and column sums
• The solution of van der Waerden's problem for permanents
• The Van der Waerden conjecture for mixed discriminants
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited in

(23)

• A faster FPTAS for counting two-rowed contingency tables
• Approximate counting of standard set-valued tableaux
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Counting subsets of contingency tables
• Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
• Efficient importance sampling for binary contingency tables
• Lower bounds for contingency tables via Lorentzian polynomials
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• scientific article; zbMATH DE number 139640 (Why is no real title available?)
• Random partitioning over a sparse contingency table
• Sampling contingency tables
• On testing Hamiltonicity of graphs
• Improved bounds for sampling contingency tables
• Majorization and the number of bipartite graphs for given vertex degrees
• Phase transition in random contingency tables with non-uniform margins
• Approximately counting integral flows and cell-bounded contingency tables
• Enumerating Contingency Tables via Random Permanents
• The Algebraic Analysis of Contingency Tables
• Sampling binary contingency tables with a greedy start
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• On the number of contingency tables and the independence heuristic
• Linear-time uniform generation of random sparse contingency tables with specified marginals
• Random sampling of contingency tables via probabilistic divide-and-conquer

Describes a project that uses

Uses Software

• LattE

This page was built for publication: An approximation algorithm for counting contingency tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057067)