Independence Models for Integer Points of Polytopes.

摘要: Independence Models for Integer Points of Polytopes by Austin Warren Shapiro Chair: Alexander I. Barvinok The integer points a high-dimensional polytope P are generally difficult to count or sample uniformly. We consider class low-complexity random models these which arise from an entropy maximization problem. From models, way “anti-concentration” results sums independent variables, we derive general, efficiently computable upper bounds on the number . make detailed study contingency tables with bounded entries, transportation truncated cuboid. provide estimates logarithm m × n specified row and column r1, , rm, c1, cn entries. These asymptotic as m,n→∞ simultaneously, given that no ri (resp., cj) is allowed exceed fixed multiple average sum sum). As application, random, uniformly selected table entries ≤ κ having sum. Responding questions raised Diaconis Efron in context statistical significance testing, show occurrence rm positively correlated when ≥ 2 sufficiently extreme. give evidence opposite true near-average values cn.