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. Link.
Atchadé, Y., G. Fort, E. Moulines, and P. Priouret. 2009.
Adaptive Markov Chain Monte Carlo: Theory and Methods. Preprint.
Atchadé, Yves. 2010.
Limit theorems for some adaptive MCMC algorithms with subgeometric kernels. Bernoulli 16, no. 1 (February): 116-154. doi:10.3150/09-BEJ199. Link.
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.
]
Best Answer
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.