Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions (Q1024896)

To overcome the bottlenecks of the Markov chain Monte Carlo (MCMC) technique in the case of multimodal target distributions, variants of algorithms, among them, there are, e.g. Metropolis-coupled MCMC (parallel tempering or swapping algorithm) and simulated tempering, have been studied. The convergence rate of an algorithm is governed by the spetral gap of the kernel, for which the decomposition approach [cf. e.g. \textit{N. Madaras} and \textit{Z. Zheng}, Random Struct. Algorithms 22, No.~1, 66--97 (2003; Zbl 1013.60074)] is generalized in the present paper. There the authors have proved that the spectral gap of the Markov chain of the swapping algorithm is bounded below by the reciprocal of a polynomial in the problem size M. It means that the swapping algorithm is a fast algorithm (in the sence of polynomial time), which is then called rapidly mixing. This argument is also applied in this paper to the nonsymmetric composition target distributions.