MCMC algorithms are a very popular method of approximately sampling from complicated probability distributions. A wide variety of MCMC schemes are available, and it is tempting to have the computer automatically "adapt" the algorithm while it runs, to improve and tune on the fly. However, natural-seeming adaptive schemes often fail to preserve the stationary distribution, thus destroying the fundamental ergodicity properties necessary for MCMC algorithms to be valid. In this talk, we review adaptive MCMC, and present simple conditions which ensure ergodicity (proved using intuitive coupling constructions, jointly with G.O. Roberts). The ideas are illustrated using a very simple example: an adaptive Metropolis algorithm on a six-point state space, animated by the java applet at robability.ca/jeff/java/adapt.html.
Group for Research in Decision Analysis