Maximum entropy Edgeworth estimates of the number of integer points in polytopes

Abstract

Abstract: The number of points $x=(x_1,x_2,...x_n)$ that lie in an integer cube $C$ in $R^n$ and satisfy the constraints ${\sum }_j{h}_{ij}(x_j)=s_i,1\le i\le d$ is approximated by an Edgeworth-corrected Gaussian formula based on the maximum entropy density $p$ on $x\in C$, that satisfies $E{\sum }_j{h}_{ij}(x_j)=s_i,1\le i\le d$. Under $p$, the variables $X_1,X_2,...X_n$ are independent with densities of exponential form. Letting $S_i$ denote the random variable ${\sum }_j{h}_{ij}(X_j)$, conditional on $S=s,X$ is uniformly distributed over the integers in $C$ that satisfy $S=s$. The number of points in $C$ satisfying $S=s$ is $p\{S=s\}\exp (I(p))$ where $I(p)$ is the entropy of the density $p$. We estimate $p\{S=s\}$ by $p_Z(s)$, the density at $s$ of the multivariate Gaussian $Z$ with the same first two moments as $S$; and when $d$ is large we use in addition an Edgeworth factor that requires the first four moments of $S$ under $p$. The asymptotic validity of the Edgeworth-corrected estimate is proved and demonstrated for counting contingency tables with given row and column sums as the number of rows and columns approaches infinity, and demonstrated for counting the number of graphs with a given degree sequence, as the number of vertices approaches infinity.

29 pages 3 tables Revision updates references,and sharpens statement and proof of theorem 2

References in corpus (1)

• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums