Independence Models for Integer Points of Polytopes.

Abstract

The integer points of a high-dimensional polytope P are generally difficult to count or sample uniformly. We consider a class of low-complexity random models for these points which arise from an entropy maximization problem. From these models, by way of "anti-concentration" results for sums of independent random variables, we derive general, efficiently computable upper bounds on the number of integer points of P.

We make a detailed study of contingency tables with bounded entries, which are the integer points of a transportation polytope truncated by a cuboid. We provide efficiently computable estimates for the logarithm of the number of m by n tables with specified row and column sums r_1, ..., r_m, c_1, ..., c_n and bounds on the entries. These estimates are asymptotic as m and n go to infinity simultaneously, given that no r_i (resp., c_j) is allowed to exceed a fixed multiple of the average row sum (resp., column sum).

As an application, we consider a random, uniformly selected table with entries in {0, 1, ..., kappa} having a given sum. Responding to questions raised by Diaconis and Efron in the context of statistical significance testing, we show that the occurrence of row sums r_1, ..., r_m is positively correlated with the occurrence of column sums c_1, ..., c_n when kappa > 1 and r_1, ..., r_m, c_1, ..., c_n are sufficiently extreme. We give evidence that the opposite is true for near-average values of r_1, ..., r_m, c_1, ..., c_n.