2016/08/15 by Vladimir Kolmogorov, Kolmogorov, Vladimir · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1608.04223
openalex publication_date 2016/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of estimating the partition function Z(β)=∑x exp(-β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=ln Z(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qln n⋅[ln q + ln ln n+ε-2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in \0\∪[1,n]. We improve the complexity to O(qln n⋅ε-2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O((ε2)/(qln n)) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ ε-2) oracle calls under a natural model of computation.