The Swapping Algorithm and Mean-Field ModelsAlgebra & Discrete Mathematics
|Speaker:||Prof. Dana Randall, Georgia Tech|
|Start time:||Thu, Dec 5 2002, 12:00PM|
Simulated tempering is a compelling Markov chain heuristic used for random sampling when other Markov chains are known to be slow. The idea is to enhance the state space with a parameter modeling temperature, and to allow the temperature to vary during the simulation. At high temperature bottlenecks (which cause slow mixing) disappear, mixing occurs, and lowering the temperature recovers the stationary distribution of interest. The swapping algorithm is a variant of this method. Recently Madras and Zheng analyzed the swapping algorithm on two bimodal distributions, including the mean-field Ising model, and showed that it is efficient. We extend these results to show that the swap algorithm is efficient for some asymmetric distributions as well. However, we also demonstrate that the swap algorithm can be exponentially slow, as it turns out to be for the mean-field Potts model.