Approximation algorithms for the normalizing constant of Gibbs distributions

Consider a family of distributions {..} where X... means that P(X=x)=exp(..H(x))/Z(.). Here Z(.) is the proper normalizing constant, equal to .xexp(..H(x)). Then {..} is known as a Gibbs distribution, and Z(.) is the partition function. This work presents a new method for approximating the partition function to a specified level of relative accuracy using only a number of samples, that is, O(ln(Z(.))ln(ln(Z(.)))) when Z(0).1. This is a sharp improvement over previous, similar approaches that used a much more complicated algorithm, requiring O(ln(Z(.))ln(ln(Z(.)))5) samples.