Parameter estimation for Gibbs distributions

We consider Gibbs distributions, which are families of probability distributions over a discrete space Omega with probability mass function of the form μ^Omegaβ(ω) propto eβ H(ω) for β in an interval [βmin, βmax] and H( ω ) ∈ 0 cup [1, n]. The partition function is the normalization factor Z(β)=sumω ∈Omegaeβ H(ω). Two important parameters of these distributions are the log partition ratio q = log tfracZ(βmax)Z(βmin) and the counts cx = |H-1(x)|. These are correlated with system parameters in a number of physical applications and sampling algorithms. Our first main result is to estimate the counts cx using roughly tilde O( fracqvarepsilon2) samples for general Gibbs distributions and tilde O( fracn2varepsilon2 ) samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we also develop algorithms to compute the partition function Z using tilde O(fracqvarepsilon2) samples for general Gibbs distributions and using tilde O(fracn2varepsilon2) samples for integer-valued distributions.