Enumerating contingency tables via random permanents

Details Enumerating contingency tables via random permanents Enumerating contingency tables via random permanents

2005-11-23

arxiv.org/abs/math/0511596v2

Mathematics

Combinatorics

19 pages, bounds are sharpened, references are added

Scientific paper

Given m positive integers R=(r_i), n positive integers C=(c_j) such that sum r_i = sum 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 (contingency tables) 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}}. We present a randomized algorithm of a polynomial in N complexity which computes a number T'=T'(R,C; W) such that T' < T < alpha(R, C) T' where alpha(R,C) = min{prod r_i! r_i^{-r_i}, prod c_j! c_j^{-c_j}} 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 x N random matrix with exponentially distributed entries and approximate the expectation by the integral T' of an efficiently computable log-concave function on R^{mn}. Applications to counting integer flows in graphs are also discussed.

Affiliated with

Also associated with

No associations

Rating

Enumerating contingency tables via random permanents does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Enumerating contingency tables via random permanents, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumerating contingency tables via random permanents will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424600