Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes

DOI10.1016/J.AAM.2010.01.004zbMATH Open1213.05015arXiv0903.5223OpenAlexW2096896614MaRDI QIDQ984027FDOQ984027

Alexander Barvinok, J. A. Hartigan

Publication date: 13 July 2010

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We describe a maximum entropy approach for computing volumes and counting integer points in polyhedra. To estimate the number of points from a particular set X in R^n in a polyhedron P in R^n, by solving a certain entropy maximization problem, we construct a probability distribution on the set X such that a) the probability mass function is constant on the intersection of P and X and b) the expectation of the distribution lies in P. This allows us to apply Central Limit Theorem type arguments to deduce computationally efficient approximations for the number of integer points, volumes, and the number of 0-1 vectors in the polytope. As an application, we obtain asymptotic formulas for volumes of multi-index transportation polytopes and for the number of multi-way contingency tables.

Full work available at URL: https://arxiv.org/abs/0903.5223

Recommendations

• Counting integer points in higher-dimensional polytopes
• Efficient random-walk methods for approximating polytope volume
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Entropy, optimization and counting
• Practical polytope volume approximation

zbMATH Keywords

entropyvolumecontingency tablecentral limit theorempolyhedronpolytopetransportation polytopeinteger points

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Computational aspects related to convexity (52B55) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Asymptotic enumeration (05A16)

Cites Work

• Title not available (Why is that?)
• The many aspects of counting lattice points in polytopes
• Information Theory and Statistical Mechanics
• Title not available (Why is that?)
• Residue formulae, vector partition functions and lattice points in rational polytopes
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• The Complexity of Three-Way Statistical Tables
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• Maximum Entropy for Hypothesis Formulation, Especially for Multidimensional Contingency Tables
• On the application of symmetric Dirichlet distributions and their mixtures to contingency tables
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

• Consistency under sampling of exponential random graph models
• Probabilistic existence of regular combinatorial structures
• Maximum likelihood estimation in the \(\beta\)-model
• Phase transition in random contingency tables with non-uniform margins
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Maximum entropy and integer partitions
• Random graphs with a given degree sequence
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Random doubly stochastic matrices: the circular law
• Smoothed counting of 0–1 points in polyhedra
• The number of graphs and a random graph with a given degree sequence
• A quick estimate for the volume of a polyhedron
• Matrices with prescribed row and column sums
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• Independent sets of a given size and structure in the hypercube
• When the degree sequence is a sufficient statistic
• Statistical properties of the single linkage hierarchical clustering estimator
• Title not available (Why is that?)

This page was built for publication: Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q984027)