Sampling contingency tables
This article is devoted to the study of random sampling from a set of contingency tables. First, the authors show that the problem of determining the exact number of contingency tables is \#P-complete. They prove this result by establishing a relationship between their problem and the computation of the \((n-1)\)-dimensional volume of the polytope \(\sum_{j=1}^{n-1} a_jy_j\leq b\), where \(0\leq y_j\leq 1\) \((j=1,\dots, n-1)\) and \(a_1,\dots, a_{n-1},b\) are given positive integers. Then they reduce the problem of sampling from the discrete set of contingency tables to the problem of sampling with near-uniform density from a contingency polytope. They show that the problem of random sampling can be solved in polynomial time if the row and column sums are large enough. This provides, under the same hypothesis as above, a polynomial time algorithm to solve the problem of counting the number of contingency tables approximately. The algorithm that they present is based on a random walk approach and it is related to volume computation from log-concave distributions.
- On the computational complexity of reconstructing lattice sets from their X-rays
- On the number of faces of certain transportation polytopes
- Polynomial-time counting and sampling of two-rowed contingency tables
- Asymptotic enumeration of integer matrices with large equal row and column sums
- 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
- Efficient importance sampling for binary contingency tables
- Analysis of convergence rates of some Gibbs samplers on continuous state spaces
- Statistical evidence in contingency tables analysis
- The many aspects of counting lattice points in polytopes
- Sequential importance sampling for multiway tables
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
- 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
- An approximation algorithm for counting contingency tables
- Rapid calculation of exact cell bounds for contingency tables from conditional frequencies
- Random walks on the vertices of transportation polytopes with constant number of sources
- Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
- A nonparametric test for symmetry based on Freeman and Halton's ideas on contingency tables
- Exact sampling and counting for fixed-margin matrices
- Fast Unimodular Counting
- Random generation of 2�n contingency tables
- Improved bounds for sampling contingency tables
- Characterizing optimal sampling of binary contingency tables via the configuration model
- Uniformly Generating Origin Destination Tables
- What does a random contingency table look like?
- Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
- Majorization and the number of bipartite graphs for given vertex degrees
- On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries
- Approximately counting integral flows and cell-bounded contingency tables
- Enumerating Contingency Tables via Random Permanents
- Approximating the volume of tropical polytopes is difficult
- 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 Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries
- Linear-time uniform generation of random sparse contingency tables with specified marginals
- Random sampling of contingency tables and partitions: two practical examples of the Burnside process
- Improved estimates for the number of non-negative integer matrices with given row and column sums
- Random generation of 2 2 2 J contingency tables
- clrng: a tool set for parallel random number generation on GPUs in R
- RSK as a linear operator
- Random sampling of contingency tables via probabilistic divide-and-conquer
- Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums
This page was built for publication: Sampling contingency tables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4345364)
