Belief-propagation-guided Monte-Carlo sampling

Abstract

A Monte-Carlo algorithm for discrete statistical models that combines the full power of the belief-propagation algorithm with the advantages of a heat-bath approach fulfilling the detailed balance is presented. First we extract randomly a subtree inside the interaction graph of the system. Second, given the boundary conditions, belief propagation is used as a perfect sampler to generate a configuration on the tree, and finally, the procedure is iterated. This approach is best adapted for locally treelike graphs and we therefore tested it on random graphs for hard models such as spin glasses, demonstrating its state-of-the art status in those cases.

Publication
Phys. Rev. B