Does waste-recycling really improve Metropolis-Hastings Monte Carlo algorithm?

DOI10.1239/JAP/1261670681arXivmath/0611949MaRDI QIDQ6478337FDOQ6478337

Benjamin Jourdain, Jean-François Delmas

Publication date: 30 November 2006

Abstract: The Metropolis Hastings algorithm and its multi-proposal extensions are aimed at the computation of the expectation $<pi,f>$ of a function $f$ under a probability measure $pi$ difficult to simulate. They consist in constructing by an appropriate acceptation/rejection procedure a Markov chain $(X_k,kgeq0)$ with transition matrix $P$ such that $pi$ is reversible with respect to $P$ and in estimating $<pi,f>$ by the empirical mean $I_n(f)=invnsu{m}_{k=1}^{n}f(X_k)$. The waste-recycling Monte Carlo (WR) algorithm introduced by physicists is a modification of the Metropolis-Hastings algorithm, which makes use of all the proposals in the empirical mean, whereas the standard Metropolis-Hastings algorithm only uses the accepted proposals. In this paper, we extend the WR algorithm into a general control variate technique and exhibit the optimal choice of the control variate in terms of asymptotic variance. We also give an example which shows that in contradiction to the intuition of physicists, the WR algorithm can have an asymptotic variance larger than the one of the Metropolis-Hastings algorithm. However, in the particular case of the Metropolis-Hastings algorithm called Boltzmann algorithm, we prove that the WR algorithm is asymptotically better than the Metropolis-Hastings algorithm.

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

This page was built for publication: Does waste-recycling really improve Metropolis-Hastings Monte Carlo algorithm?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478337)