Here is a simulation of a simple one-dimensional Metropolis (MCMC)
algorithm, including an adaptive option.
(If you have trouble running the applet,
see these notes.)
See the chain run!
An explanation is below.
The applet accepts the following keyboard inputs. (You may need to
"click" on the applet first.)
Use the numbers '0' through '9' to set the animation speed level higher
Use 'r' to restart the simulation, or 'z' to just zero the empirical count,
or 's' to toggle whether or not to show the (black) empirical distribution.
- Use 'g' to cycle the target distribution between
certain specific values,
and randomly-generated values,
and a special "counter-example" target.
Use '+' and '-' to increase/decrease the number of states
(and restart the simulation).
Use 'n' to never adapt (default), or 'y' to always adapt, or
'd' to adapt with probability
1/iteration, or 'o' to fix gamma=1, or 't' to fix gamma=2, or
'F' to fix gamma=50.
Use 'p' and 'm' to increase/decrease the current value of gamma.
- Use 'A' to jump to the left-most state,
or 'B' to jump to the right-most state.
Use '>' and '<' to increase/decrease the target probability of state 2
(and restart the simulation) for the counter-example target.
At fast animation speed levels, you can press any other key (e.g.
'space') at any time to get an instantaneous snapshot of the iteration
This algorithm runs a random-walk Metropolis (RWM) algorithm, for the target
probability distribution graphed with blue bars.
The algorithm's current state is indicated by the black disk.
The proposal distribution is uniform on the white disks, from x-gamma to
x+gamma (but excluding x itself). The yellow disk then shows the actual
The yellow disk turns green if the proposal is accepted, or red if
it is rejected. The (black) current state is updated accordingly.
The empirically estimated distribution is graphed with black bars. If the
simulation correctly preserved stationarity of the target distribution,
then the black and blue bars should converge in height.
Comparison of means: The small vertical blue line at the top shows
the target mean, while the small vertical black line shows the current
empirical mean. If the simulation correctly preserved stationarity,
then the two lines should converge.
*If* adaption is turned on (with 'y'),
the algorithm "adapts", by increasing gamma by 1
if the previous proposal was accepted, or decreasing gamma by 1 (to a
minimum of 1) if the previous proposal was rejected.
With the adapt option turned on (with 'y'),
once the chain reaches state 1 with gamma=1,
it tends to get stuck there for a very long time, causing the
empirical distribution to significantly overweight state 1.
This shows that, counter-intuitively, this adaptive algorithm does
not preserve stationarity of the target distribution.
However, if we instead select diminishing adaption probabilities
(with 'd'), or no adaptions (with 'n'), then convergence is preserved.
Remark: The example presented here is on a discrete
state space, but this is not essential. Indeed, if the above target and
proposal distributions are each convolved with a Normal(0, 0.000001)
distribution, this produces an example on a continuous state space
(with continuous, everywhere-positive densities) which has virtually
identical behaviour, and similarly fails to converge.
For further discussion of adaptive MCMC algorithms and related examples,
G.O. Roberts and J.S. Rosenthal,
Examples of Adaptive MCMC.
J. Comp. Graph. Stat. 18(2) (2009), 349-367.
G.O. Roberts and J.S. Rosenthal,
Coupling and Ergodicity of Adaptive MCMC.
J. Appl. Prob. 44 (2007), 458-475.
AMCMC: An R/C package for
running Adaptive MCMC.
Comp. Stat. Data Anal. 51 (2007), 5467-5470.
K. Latuszynski, G.O. Roberts, and J.S. Rosenthal,
Adaptive Gibbs samplers and related MCMC methods.
Ann. Appl. Prob., to appear.
Y.F. Atchadé and J.S. Rosenthal,
On Adaptive Markov Chain Monte Carlo
Bernoulli 11 (2005), 815-828.
H. Haario, E. Saksman, and J. Tamminen,
An adaptive Metropolis algorithm.
Bernoulli 7 (2001), 223-242.
C. Andrieu and E. Moulines,
the Ergodicity Properties of some Adaptive MCMC Algorithms.
Ann. Appl. Prob. 16 (2006), 1462-1505.
P. Giordani and R. Kohn,
Adaptive Independent Metropolis-Hastings
by Fast Estimation of Mixtures of Normals. Preprint, 2006.
E. Turro, N. Bochkina, A.M.K. Hein, and S. Richardson (2007),
Bioconductor package for the Bayesian integrated analysis of
Affymetrix GeneChips. BMC Bioinformatics 8 (2007), 439-448.
S. Richardson, L. Bottolo, and J.S. Rosenthal,
Bayesian models for sparse
regression analysis of high dimensional data.
Valencia IX Bayesian Meeting conference proceedings, 2010.
Applet by Jeffrey S. Rosenthal
[Return to my Applets Page / Home Page]