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

Question

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.

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. 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.

]

Answer 1

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.

Answer 2

You can improve the acceptance rate using delayed rejection as described in Tierney, Mira (1999). It is based on a second proposal function and a second acceptance probability, which guarantees the Markov chain is still reversible with the same invariant distribution: you have to be cautious since "it is easy to construct adaptive methods that might seem to work but in fact sample from the wrong distribution".

Answer 3

The approaches suggested by users wok and robertsy cover the most commonly cited examples of what you're looking for that I know of. Just to expand on those answers, Haario and Mira wrote a paper in 2006 that combines the two approaches, an approach they call DRAM (delayed rejection adaptive Metropolis).

Andrieu has a nice treatment of various different adaptive MCMC approaches (pdf) which covers Haario 2001 but also discusses various alternatives that have been proposed in recent years.