# Can I change the proposal distribution in random-walk MH MCMC without affecting Markovianity?

Random walk Metropolis-Hasitings with symmetric proposal

$q(x|y)= g(|y-x|)$ has the property that the acceptance probability

$$P(accept\ y) = \min\{1, f(y)/f(x)\}$$

does not depend on proposal $g(\cdot)$.

Does that mean that I can change the $g(\cdot)$ as a function of previous performance of the chain, without affecting the markovianity of the chain?

Of particular interest to me is the adjustment of the scaling of Normal proposal as a function of acceptance rate.

Would also greatly appreciate if someone can point out to the adaptation algorithms used in practice for this type of problem.

Many thanks.

[edit: Starting with the references given by robertsy and wok I found the following references on MH adaptive algorithms:

Andrieu, Christophe, and Éric Moulines. 2006.
On the Ergodicity Properties of Some Adaptive MCMC Algorithms. The Annals of Applied Probability 16, no. 3: 1462-1505. http://www.jstor.org/stable/25442804.

Andrieu, Christophe, and Johannes Thoms.
2008. A tutorial on adaptive MCMC. Statistics and Computing 18, no. 4 (12): 343-373. doi:10.1007/s11222-008-9110-y. http://www.springerlink.com/content/979087678366r78v/.

Atchadé, Y., G. Fort, E. Moulines, and P. Priouret. 2009.
Adaptive Markov Chain Monte Carlo: Theory and Methods. Preprint.

Limit theorems for some adaptive MCMC algorithms with subgeometric kernels. Bernoulli 16, no. 1 (February): 116-154. doi:10.3150/09-BEJ199. http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bj/1265984706&page=record.

Cappé, O., S. J Godsill, and E. Moulines. 2007.
An overview of existing methods and recent advances in sequential Monte Carlo. Proceedings of the IEEE 95, no. 5: 899-924.

Giordani, Paolo. 2010.
Adaptive Independent Metropolis–Hastings by Fast Estimation of Mixtures of Normals. Journal of Computational and Graphical Statistics 19, no. 2 (6): 243-259. doi:10.1198/jcgs.2009.07174. http://pubs.amstat.org/doi/abs/10.1198/jcgs.2009.07174.

Latuszynski, Krzysztof, Gareth O Roberts, and Jeffrey S Rosenthal. 2011.
Adaptive Gibbs samplers and related MCMC methods. 1101.5838 (January 30). http://arxiv.org/abs/1101.5838.

Pasarica, C., and A. Gelman. 2009.
Adaptively scaling the Metropolis algorithm using expected squared jumped distance. Statistica Sinica.

Roberts, Gareth O. 2009.
Examples of Adaptive MCMC. Journal of Computational and Graphical Statistics 18, no. 2 (6): 349-367. doi:10.1198/jcgs.2009.06134. http://pubs.amstat.org/doi/abs/10.1198/jcgs.2009.06134.

]

-
How come you don't have +100 bonus from your SO record? –  mbq Feb 16 '11 at 10:57
@mbq, probably because I created this account long ago when I was 0 on OS as well...pity, 100 on CW looks like a big deal, since you must be a real chap to answer stuff in here :) –  VitoshKa Feb 16 '11 at 11:11
You can get the bonus by clearing all associations and then associating accounts again. –  wok Feb 16 '11 at 15:37
thanks @wok, nice to be reach:) –  VitoshKa Feb 16 '11 at 16:15

I think that this paper from Heikki Haario et al. will give you the answer you need. The markovianity of the chain is affected by the adaptation of the proposal density, because then a new proposed value depends not only of the previous one but on the whole chain. But it seems that the sequence has still the good properties if great care is taken.

-
thanks robertsy, for good reference. indeed the process is not markov. Even if acceptance probability is independent of the past, the transition kernel of the process is a function of the proposal density and thus depends on the whole chain. –  VitoshKa Feb 16 '11 at 16:07