TPA: A New Method for Approximate Counting

Abstract

Many high dimensional integrals can be reduced to the problem of finding the relative measure of two sets. Often one set will be exponentially larger than the other. A standard method of dealing with this problem is to interpolate between the sets with a series of nested sets where neighboring nested sets have relative measures bounded above by a constant. Choosing these sets can be very difficult in practice. Here a new approach that creates a randomly drawn sequence of such sets is presented. This procedure gives faster approximation algorithms and a well-balanced set of nested sets that are essential to building effective tempering and annealing algorithms.