Scaling analysis of multiple-try MCMC methods

Multiple-try methods are extensions of the Metropolis algorithm in which the next state of the Markov chain is selected among a pool of proposals. These techniques have witnessed a recent surge of interest because they lend themselves easily to parallel implementations. We consider extended versions of these methods in which some dependence structure is introduced in the proposal set, extending earlier work by Craiu and Lemieux (2007). We show that the speed of the algorithm increases with the number of candidates in the proposal pool and that the increase in speed is favored by the introduction of dependence among the proposals. A novel version of the hit-and-run algorithm with multiple proposals appears to be very successful.