APPROXIMATION ALGORITHMS FOR THE NORMALIZING CONSTANT OF GIBBS DISTRIBUTIONS

• 成果类型: Article
• 署名作者: Huber, Mark
• 署名单位: Claremont Colleges; Claremont McKenna College; Claremont Graduate University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1015
• 发表日期: 2015
• 页码: 974-985
• 关键词: simulation; chains

摘要

Consider a family of distributions {pi(beta)} where X similar to pi(beta) means that P(X = x) = exp(-beta H(x))/Z(beta). Here Z(beta) is the proper normalizing constant, equal to Sigma(x) exp(-beta H(x)). Then {pi(beta)} is known as a Gibbs distribution, and Z(beta) 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(beta) ln(ln(Z(beta)))) when Z(0) >= 1. This is a sharp improvement over previous, similar approaches that used a much more complicated algorithm, requiring O(ln(Z(beta) ln(ln(Z(beta)))(5)) samples.