Enumerating Contingency Tables via Random Permanents

Source abstract

Given m positive integers R = ( r i ), n positive integers C = ( c j ) such that Σ r i = Σ c j = N , and mn non-negative weights W =( w ij ), we consider the total weight T = T ( R, C ; W ) of non-negative integer matrices D =( d ij ) with the row sums r i , column sums c j , and the weight of D equal to $\prod w_{ij}^{d_{ij}}$ . For different choices of R , C , and W , the quantity T ( R,C ; W ) specializes to the permanent of a matrix, the number of contingency tables with prescribed margins, and the number of integer feasible flows in a network. We present a randomized algorithm whose complexity is polynomial in N and which computes a number T ′= T ′( R,C ; W ) such that T ′ ≤ T ≤ α( R,C ) T ′ where $\alpha(R,C) = \min \bigl\{\prod r_i! r_i^{-r_i}, \ \prod c_j! c_j^{-c_j} \bigr\} N^N/N!$ . In many cases, ln T ′ provides an asymptotically accurate estimate of ln T . The idea of the algorithm is to express T as the expectation of the permanent of an N × N random matrix with exponentially distributed entries and approximate the expectation by the integral T ′ of an efficiently computable log-concave function on ℝ mn .