Small-World MCMC and Convergence to Multi-modal Distributions: From Slow Mixing to Fast Mixing

Yongtao Guan, Stephen M. Krone


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.