SUPPRESSING RANDOM WALKS IN MARKOV CHAIN MONTE CARLO
USING ORDERED OVERRELAXATION
Radford M. Neal
Dept. of Statistics and Dept. of Computer Science
University of Toronto
21 June 1995
Markov chain Monte Carlo methods such as Gibbs sampling and simple
forms of the Metropolis algorithm typically move about the
distribution being sampled via a random walk. For the complex,
high-dimensional distributions commonly encountered in Bayesian
inference and statistical physics, the distance moved in each
iteration of these algorithms will usually be small, because it is
difficult or impossible to transform the problem to eliminate
dependencies between variables. The inefficiency inherent in taking
such small steps is greatly exacerbated when the algorithm operates
via a random walk, as in such a case moving to a point n steps away
will typically take around n^2 iterations. Such random walks can
sometimes be suppressed using ``overrelaxed'' variants of Gibbs
sampling (a.k.a. the heatbath algorithm), but such methods have
hitherto been largely restricted to problems where all the full
conditional distributions are Gaussian. I present an overrelaxed
Markov chain Monte Carlo algorithm based on order statistics that is
more widely applicable. In particular, the algorithm can be applied
whenever the full conditional distributions are such that their
cumulative distribution functions and inverse cumulative distribution
functions can be efficiently computed. The method is demonstrated on
an inference problem for a simple hierarchical Bayesian model.