  We consider Gibbs distributions, which are families of probability
distributions over a discrete space $\Omega$ with probability mass function of
the form $\mu^\Omega_\beta(\omega) \propto e^{\beta H(\omega)}$ for $\beta$ in
an interval $[\beta_{\min}, \beta_{\max}]$ and $H( \omega ) \in \{0 \} \cup [1,
n]$. The partition function is the normalization factor $Z(\beta)=\sum_{\omega
\in\Omega}e^{\beta H(\omega)}$.
  Two important parameters of these distributions are the log partition ratio
$q = \log \tfrac{Z(\beta_{\max})}{Z(\beta_{\min})}$ and the counts $c_x =
|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 $c_x$ using roughly $\tilde
O( \frac{q}{\varepsilon^2})$ samples for general Gibbs distributions and
$\tilde O( \frac{n^2}{\varepsilon^2} )$ 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(\frac{q}{\varepsilon^2})$ samples for general
Gibbs distributions and using $\tilde O(\frac{n^2}{\varepsilon^2})$ samples for
integer-valued distributions.

Data Structures and Algorithms;Computational Complexity;Discrete Mathematics;Probability