Monte Carlo Methods for the Ferromagnetic Potts Model Using Factor Graph Duality

摘要

We consider the problem of estimating the partition function of theferromagnetic $q$-state Potts model. We propose an importance samplingalgorithm in the dual of the normal factor graph representing the model. Thealgorithm can efficiently compute an estimate of the partition function whenthe coupling parameters of the model are strong (corresponding to models at lowtemperature) or when the model contains a mixture of strong and weak couplings.We show that, in this setting, the proposed algorithm significantly outperformsthe state of the art methods.