Speaker
Description
David Harris and Vladimir Kolmogorov
Abstract: A central problem in computational statistics is to convert a procedure for \emph{sampling} combinatorial objects into a procedure for \emph{counting} those objects, and vice versa. We will consider sampling problems which come from \emph{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 \emph{partition function} is the normalization factor $Z(\beta)=\sum_{\omega \in\Omega}e^{\beta H(\omega)}$, and the \emph{log partition ratio} is defined as $q = \frac{\log Z(\beta_{max})}{Z(\beta_{min})}$
We develop a number of algorithms to estimate the counts $c_x$ using roughly
$\tilde O( \frac{q}{\epsilon^2})$ samples for general Gibbs distributions and $\tilde O( \frac{n^2}{\epsilon^2} )$ samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.