  Markov chain Monte Carlo is an inherently serial algorithm. Although
likelihood calculations for individual steps can sometimes be parallelized, the
serial evolution of the process is widely viewed as incompatible with
parallelization, offering no speedup for samplers which require large numbers
of iterations to converge to equilibrium. We provide a methodology for
parallelizing Markov chain Monte Carlo across large numbers of independent,
asynchronous processors. Our approach uses a partitioning and weight estimation
scheme to combine independent simulations run on separate processors into
rigorous Monte Carlo estimates. The method is originally motivated by sampling
multimodal target distributions, where we see an exponential speedup in running
time. However we show that the approach is general-purpose and applicable to
all Markov chain Monte Carlo simulations, and demonstrate speedups proportional
to the number of available processors on slowly mixing chains with unimodal
target distributions. The approach is simple and easy to implement, and
suggests additional directions for further research.
