  We give conditions under which a Markov chain constructed via parallel or
simulated tempering is guaranteed to be rapidly mixing, which are applicable to
a wide range of multimodal distributions arising in Bayesian statistical
inference and statistical mechanics. We provide lower bounds on the spectral
gaps of parallel and simulated tempering. These bounds imply a single set of
sufficient conditions for rapid mixing of both techniques. A direct consequence
of our results is rapid mixing of parallel and simulated tempering for several
normal mixture models, and for the mean-field Ising model.
