Characterizing optimal sampling of binary contingency tables via the configuration model
From MaRDI portal
Publication:4909199
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3906527 (Why is no real title available?)
- A Sequential Algorithm for Generating Random Graphs
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
- Asymptotics and random matrices with row-sum and column sum-restrictions
- Efficient importance sampling for binary contingency tables
- Expansion properties of a random regular graph after random vertex deletions
- Generalized Monte Carlo significance tests
- On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
- Probability and Computing
- Sampling binary contingency tables with a greedy start
- Sampling contingency tables
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- The complexity of computing the permanent
- The probability that a random multigraph is simple
Cited in
(6)- On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
- The probability that a random multigraph is simple. II
- The giant component of the directed configuration model revisited
- Rankings in directed configuration models with heavy tailed in-degrees
- Limit laws for self-loops and multiple edges in the configuration model
- The diameter of the directed configuration model
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)
