Mean-field Potts and random-cluster dynamics from high-entropy initializations

Abstract

A common obstruction to efficient sampling from high-dimensional distributions with Markov chains is the multimodality of the target distribution because they may get trapped far from stationarity. Still, one hopes that this is only a barrier to the mixing of Markov chains from worst-case initializations and can be overcome by choosing high-entropy initializations, for example, a product or weakly correlated distribution. Ideally, from such initializations, the dynamics would escape from the saddle points separating modes quickly and spread its mass between the dominant modes with the correct probabilities. In this paper, we study convergence from high-entropy initializations for the random-cluster and Potts models on the complete graph—two extensively studied high-dimensional landscapes that pose many complexities like discontinuous phase transitions and asymmetric metastable modes. We study the Chayes–Machta and Swendsen–Wang dynamics for the mean-field random-cluster model and the Glauber dynamics for the Potts model. We sharply characterize the set of product measure initializations from which these Markov chains mix rapidly, even though their mixing times from worst-case initializations are exponentially slow. Our proofs require careful approximations of projections of high-dimensional Markov chains (which are not themselves Markovian) by tractable one-dimensional random processes, followed by analysis of the latter’s escape from saddle points separating stable modes.