2019/04/05 by Harris, David G., Kolmogorov, Vladimir
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1904.03139
A central problem in computational statistics is to convert a procedure for sampling combinatorial from an objects into a procedure for counting those objects, and vice versa. Weconsider sampling problems coming from *Gibbs distributions*, which are probability distributions of the form μΩβ(ω) ∝ eβH(ω) for β in an interval [βmin, βmax] and H( ω) ∈ \0 \ ∪ [1, n]. The *partition function* is the normalization factor Z(β)=∑ω∈ΩeβH(ω). Two important parameters are the log partition ratio q = log \tfracZ(βmax)Z(βmin) and the vector of counts cx = |H-1(x)|. Our first result is an algorithm to estimate the counts cx using roughly O( (q)/(ε2)) samples for general Gibbs distributions and O( (n2)/(ε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. We develop a key subroutine for global estimation of the partition function. Specifically, we produce a data structure to estimate Z(β) for all values β, without further samples. Constructing the data structure requires O((q log n)/(ε2)) samples for general Gibbs distributions and O((n2 log n)/(ε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(βmax) using O((q)/(ε2)) samples. We also show that this complexity is optimal as a function of n and q up to logarithmic terms.