  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 criteria 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 influence both the dynamics and the empirical
measure. While theoretically optimal, this limit is not computationally
feasible when the number of temperatures is large, and so variations that are
easy to implement and nearly optimal are also developed.
