Independence Models for Integer Points of Polytopes.

Polytope;Integer Point;Lattice Point;Littlewood-Offord;Maximum Entropy;Contingency Table;Mathematics;Science;Mathematics

Shapiro, Austin WarrenVershynin, Roman ;

University of Michigan

关键词: Polytope;    Integer Point;    Lattice Point;    Littlewood-Offord;    Maximum Entropy;    Contingency Table;    Mathematics;    Science;    Mathematics;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/86295/auspex_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.