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 [\min, \max] and H( \omega ) \in \{0 \} \cup [1, n]. The partition function is the normalization factor Z(\beta)=\omega \in\Omegae^{\beta H(\omega)}. Two important parameters of these distributions are the  partition ratio q = \log Z(\beta_{\max)}{Z(\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 values c_x using roughly \tilde O( q{\varepsilon^2}) samples for general Gibbs distributions and \tilde O( 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 and perfect matchings in a graph. A key subroutine we develop is to estimate the partition function Z ; specifically, we generate a data structure capable of estimating Z(\beta) for all \emph{ values \beta, without further samples. Constructing the data structure requires %DIFDELCMD < \tilde %%% O(\frac{q{\varepsilon^2}} {\varepsilon^2}} ) samples for general Gibbs distributions and %DIFDELCMD < \tilde %%% O(\frac{n^2{\varepsilon^2}} {\varepsilon^2} + n \log q} ) samples for integer-valued distributions. This improves over a prior algorithm of Kolmogorov (2018 ) which computes the single point estimate Z(\beta _{\max) using }%DIFDELCMD < \tilde %%% O( \frac{q{\varepsilon^2}}  ) samples. We show matching lower bounds, demonstrating that this complexity is optimal as a function of n and q up to logarithmic terms.
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 [\min, \max] and H( \omega ) \in \{0 \} \cup [1, n]. The partition function is the normalization factor Z(\beta)=\omega \in\Omegae^{\beta H(\omega)}. Two important parameters of these distributions are the log partition ratio q = \log Z(\beta_{\max)}{Z(\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( q{\varepsilon^2}) samples for general Gibbs distributions and \tilde O( 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 and perfect matchings in a graph. We develop a key subroutine to estimate the partition function Z . Specifically, it generates a data structure to estimate Z(\beta) for \emph{all values \beta, without further samples. Constructing the data structure requires %DIFDELCMD < \tilde %%% {\varepsilon^2}} O(\frac{q \log n{\varepsilon^2}} ) samples for general Gibbs distributions and %DIFDELCMD < \tilde %%% {\varepsilon^2}} O(\frac{n^2 \log n{\varepsilon^2} + n \log q} ) samples for integer-valued distributions. This improves over a prior algorithm of Huber (2015 ) which computes a single point estimate Z(\beta ) using }%DIFDELCMD < \tilde %%% {\varepsilon^2}} _\max) using O( q \log n( \log q + \log \log n + \varepsilon^{-2 ) samples. We show matching lower bounds, demonstrating that this complexity is optimal as a function of n and q up to logarithmic terms.
R
Gibbs distributions
Gibbs distributions
A
log
R
values
counts
R
A key subroutine we develop is
We develop a key subroutine
R
; specifically, we generate
. Specifically, it generates
R
capable of estimating
to estimate
D
all
A
all
D
O(\frac{q
A
O(\frac{q \log n
D
O(\frac{n^2
A
O(\frac{n^2 \log n
R
Kolmogorov (2018
Huber (2015
R
the
a
D
_{\max
D
O( \frac{q
A
_\max) using O( q \log n( \log q + \log \log n + \varepsilon^{-2