On the Infinite Swapping Limit for Parallel Tempering

Parallel tempering, also known as replica exchange sampling, is an important method for simulating complex systems. In this algorithm simulations are conducted in parallel at a series of temperatures, and the key feature of the algorithm is a swap mechanism that exchanges configurations between the parallel simulations at a given rate. The mechanism is designed to allow the low temperature system of interest to escape from deep local energy minima where it might otherwise be trapped via those swaps with the higher temperature components. In this paper we introduce a performance criterion for such schemes based on large deviation theory and argue that the rate of convergence is a monotone increasing function of the swap rate. This motivates the study of the limit process as the swap rate goes to infinity. We construct a scheme which is equivalent to this limit in a distributional sense but which involves no swapping at all. Instead, the effect of the swapping is captured by a collection of weights that inf...