Enumerating Contingency Tables via Random Permanents

by: Alexander Barvinok

Combinatorics, Probability and Computing, Vol. 17, No. 01. (2007), pp. 1-19.

View FullText article

Cambridge University Press

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

OriginalLurch

Find related articles with these CiteULike tags

test

Abstract

Given m positive integers R = (ri), n positive integers C = (cj) such that Σri = Σcj = N, and mn non-negative weights W=(wij), we consider the total weight T=T(R, C; W) of non-negative integer matrices D=(dij) with the row sums ri, column sums cj, and the weight of D equal to <img src="/fulltext_content/CPC/CPC17_01/S0963548307008668_inline1.gif" alt="$∏ w_ij^d_ij$"></img>. 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 <img src="/fulltext_content/CPC/CPC17_01/S0963548307008668_inline2.gif" alt="$α(R,C) = \min \bigl{∏ r_i! r_i^-r_i, \ ∏ c_j! c_j^-c_j \bigr} N^N/N!$"></img>. 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 <img src="/fulltext_content/CPC/CPC17_01/xs211D.gif" alt="xs211D"></img>mn.

@article{citeulike:2678237, abstract = {Given m positive integers R = (ri), n positive integers C = (cj) such that \&\#931;ri = \&\#931;cj = N, and mn non-negative weights W=(wij), we consider the total weight T=T(R, C; W) of non-negative integer matrices D=(dij) with the row sums ri, column sums cj, and the weight of D equal to <img src="/fulltext\_content/CPC/CPC17\_01/S0963548307008668\_inline1.gif" alt="\$\prod w\_{ij}^{d\_{ij}}\$"></img>. 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\&\#8242;=T\&\#8242;(R,C;W) such that T\&\#8242; \&\#8804; T \&\#8804; \&\#945;(R,C)T\&\#8242; where <img src="/fulltext\_content/CPC/CPC17\_01/S0963548307008668\_inline2.gif" alt="\$\alpha(R,C) = \min \bigl\{\prod r\_i! r\_i^{-r\_i}, \ \prod c\_j! c\_j^{-c\_j} \bigr\} N^N/N!\$"></img>. In many cases, ln T\&\#8242; 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 \&\#215; N random matrix with exponentially distributed entries and approximate the expectation by the integral T\&\#8242; of an efficiently computable log-concave function on <img src="/fulltext\_content/CPC/CPC17\_01/xs211D.gif" alt="xs211D"></img>mn.}, author = {Barvinok, Alexander }, citeulike-article-id = {2678237}, journal = {Combinatorics, Probability and Computing}, keywords = {test}, number = {01}, pages = {1--19}, posted-at = {2008-04-16 15:47:19}, priority = {2}, title = {Enumerating Contingency Tables via Random Permanents}, url = {http://journals.cambridge.org/action/displayAbstract?fromPage=online\&aid=1582952}, volume = {17}, year = {2007} }

RIS record

TY - JOUR ID - citeulike:2678237 L3 - citeulike-article-id:2678237 TI - Enumerating Contingency Tables via Random Permanents JF - Combinatorics, Probability and Computing VL - 17 IS - 01 SP - 1 EP - 19 N2 - Given m positive integers R = (ri), n positive integers C = (cj) such that Σri = Σcj = N, and mn non-negative weights W=(wij), we consider the total weight T=T(R, C; W) of non-negative integer matrices D=(dij) with the row sums ri, column sums cj, and the weight of D equal to <img src="/fulltext_content/CPC/CPC17_01/S0963548307008668_inline1.gif" alt="$\prod w_{ij}^{d_{ij}}$"></img>. 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 <img src="/fulltext_content/CPC/CPC17_01/S0963548307008668_inline2.gif" alt="$\alpha(R,C) = \min \bigl\{\prod r_i! r_i^{-r_i}, \ \prod c_j! c_j^{-c_j} \bigr\} N^N/N!$"></img>. 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 <img src="/fulltext_content/CPC/CPC17_01/xs211D.gif" alt="xs211D"></img>mn. KW - test AU - Barvinok, Alexander PY - 2007//27/ UR - http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=1582952 ER -

RIS BibTeX