Small-world MCMC and convergence to multi-modal distributions: From slow mixing to fast mixing

We compare convergence rates of Metropolis.Hastings chains to multi-modal target distributions when the proposal distributions can be of .local. and .small world. type. In particular, we show that by adding occasional long-range jumps to a given local proposal distribution, one can turn a chain that is .slowly mixing. (in the complexity of the problem) into a chain that is .rapidly mixing.. To do this, we obtain spectral gap estimates via a new state decomposition theorem and apply an isoperimetric inequality for log-concave probability measures. We discuss potential applicability of our result to Metropolis-coupled Markov chain Monte Carlo schemes.