Characterizing optimal sampling of binary contingency tables via the configuration model
From MaRDI portal
Publication:4909199
DOI10.1002/RSA.20403zbMATH Open1257.62065arXiv1007.1214OpenAlexW1546163884MaRDI QIDQ4909199FDOQ4909199
Authors: Alexandre Stauffer, Jose Blanchet 
Publication date: 12 March 2013
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Abstract: A binary contingency table is an m x n array of binary entries with prescribed row sums r=(r_1,...,r_m) and column sums c=(c_1,...,c_n). The configuration model for uniformly sampling binary contingency tables proceeds as follows. First, label N=sum_{i=1}^{m} r_i tokens of type 1, arrange them in m cells, and let the i-th cell contain r_i tokens. Next, label another set of tokens of type 2 containing N=sum_{j=1}^{n}c_j elements arranged in n cells, and let the j-th cell contain c_j tokens. Finally, pair the type-1 tokens with the type-2 tokens by generating a random permutation until the total pairing corresponds to a binary contingency table. Generating one random permutation takes O(N) time, which is optimal up to constant factors. A fundamental question is whether a constant number of permutations is sufficient to obtain a binary contingency table. In the current paper, we solve this problem by showing a necessary and sufficient condition so that the probability that the configuration model outputs a binary contingency table remains bounded away from 0 as N goes to infty. Our finding shows surprising differences from recent results for binary symmetric contingency tables.
Full work available at URL: https://arxiv.org/abs/1007.1214
Recommendations
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- The complexity of computing the permanent
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- The probability that a random multigraph is simple
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Probability and Computing
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
- Sampling contingency tables
- Title not available (Why is that?)
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotics and random matrices with row-sum and column sum-restrictions
- Efficient importance sampling for binary contingency tables
- Generalized Monte Carlo significance tests
- On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
- Sampling binary contingency tables with a greedy start
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- Expansion properties of a random regular graph after random vertex deletions
- A Sequential Algorithm for Generating Random Graphs
Cited In (7)
- On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
- Rankings in directed configuration models with heavy tailed in-degrees
- The giant component of the directed configuration model revisited
- Limit laws for self-loops and multiple edges in the configuration model
- The diameter of the directed configuration model
- Negative examples for sequential importance sampling of binary contingency tables
- The probability that a random multigraph is simple. II
This page was built for publication: Characterizing optimal sampling of binary contingency tables via the configuration model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909199)
