Improved Bound for Mixing Time of Parallel Tempering

A key problem in statistics, computer science, and statistical physics is to draw samples given access to the probability density function, up to a constant of proportionality. Because it is often hard to draw independent samples from the target distribution directly, Markov Chain Monte Carlo(MCMC) methods are often used instead. However, a common difficulty for typical MCMC methods is that for strongly multimodal distributions, MCMC methods take unreasonably long time to reach stationarity. Parallel tempering is an MCMC algorithm that is widely used in sampling from multimodal distributions. Though highly effective in practice, theoretical guarantees on its performance are limited. Since large spectral gap implies fast mixing, a common way to obtain an upper bound on mixing time is to obtain a lower bound on spectral gap.