Necessary and Sufficient Conditions for Efficient Counting of Binary Contingency Tables under the Configuration Model (with A. Stauffer).

Summary:

A contingency table is an array of size m by n of binary entries. The row and column sums are given natural numbers (r_1,…,r_m) and (c_1,…,c_n). The configuration model produces tables (not necessarily binary) as follows. Let’s say that r_1+…+r_m=N=c_1+…+c_n. Suppose that you have N tokes of type A, labeled from 1 to N and divided in m cells R1 up to Rm. The first r_1 type A tokens in cell R1; r_1+1 to r_2+r_1 type A tokens in cell R2, etc…). An analogous arrangement is in place for type B tokens in cells C1 up to Cn. Match type A and type B tokens according to a random permutation and count matches between Ri are Cj cells. Place this value in the entry (i,j) of the table. IF the table is binary, then it is a sample from the target uniform distribution. The paper characterizes exactly the class of input (r_i’s and c_j’s) for which a bounded (as n and m tend to infinity) number of trials is required to obtain a binary table. This paper extends a result of Svante Janson (Combin. Probab. Comput. 18 (2009), no. 1-2, 205-225) on the case in which c_i’s and r_j’s are equal. Surprisingly, despite the models being somewhat close, the condition is qualitative very different.

Bibtex:

@Article{BlanStau2009,

author = {J. Blanchet and A. Stauffer},

title = {Necessary and sufficient conditions for efficient counting of binary contingency tables under the configuration model},

journal = {Pre-print},

year = { },

volume = {},

pages = {}

}