Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
The Swapping Algorithm and Mean-Field ModelsAlgebra & Discrete Mathematics
|Speaker: ||Prof. Dana Randall, Georgia Tech|
|Location: ||693 Kerr|
|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.