Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes

By Alexander I. Barvinok. 2007

46 citations recorded by the source corpus.

We prove an asymptotic estimate for the number of mxn non-negative integer matrices (contingency tables) with prescribed row and column sums and, more generally, for the number of integer feasible flows in a network. Similarly, we estimate the volume of the polytope of mxn non-negative real matrices with prescribed row and column sums. Our estimates are solutions of convex optimization problems and hence can be computed efficiently. As a corollary, we show that if row sums R=(r_1, ..., r_m) and column sums C=(c_1, ..., c_n) with r_1 + ... + r_m =c_1 + ... +c_n =N are sufficiently far from constant vectors, then, asymptotically, in the uniform probability space of the mxn non-negative integer matrices with the total sum N of entries, the event consisting of the matrices with row sums R and the event consisting of the matrices with column sums C are positively correlated.

Subfields: Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ef854e82740dd7753cb1befadefa32d7b87b497c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. John Hartigan
  2. Alexander I. Barvinok
  3. Sariel Har-Peled
  4. Leo Liberti
  5. Francis R. Bach
  6. Robert Chares
  7. J. D. Loera
  8. Pablo A. Parrilo

In Statistics and Probability

  1. John Hartigan
  2. Alexander I. Barvinok
  3. Sivaraman Balakrishnan
  4. Chaopeng Shen
  5. Inderjit S. Dhillon
  6. George M. Church
  7. Naftali Tishby
  8. Yevgeny Seldin

Citations in the corpus