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

Technical Report No. 9508, Dept. of Statistics (June 1995), 22 pages:
postscript,
pdf.

Also available
from arXiv.org.

**Associated reference:**
This paper has been revised for a book chapter:
Neal, R. M. (1998) ``Suppressing random walks in Markov chain Monte Carlo
using ordered overrelaxation'', in M. I. Jordan (editor)
*Learning in Graphical Models*, pp. 205-228, Dordrecht: Kluwer
Academic Publishers:
abstract,
postscript,
pdf.