2010/07/07 by José Blanchet, Jose Blanchet, Blanchet, Jose +2
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #cs.DM #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.1007.1214
openalex publication_date 2010/07/07 · arxiv created 2011/10/11 · arxiv updated 2011/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A binary contingency table is an m x n array of binary entries with prescribed row sums r=(r1,...,rm) and column sums c=(c1,...,cn). The configuration model for uniformly sampling binary contingency tables proceeds as follows. First, label N=∑i=1m ri tokens of type 1, arrange them in m cells, and let the i-th cell contain ri tokens. Next, label another set of tokens of type 2 containing N=∑j=1ncj elements arranged in n cells, and let the j-th cell contain cj 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 ∞. Our finding shows surprising differences from recent results for binary symmetric contingency tables.