# Encyclopedia of Markov chain Monte Carlo methods

Dec 18, 2020 · 5 minute read · CodingI started this encyclopedic overview because in the Markov chain Monte Carlo (MCMC) community many people call the same or similar concepts by very different names. Please let me know, if you have suggestions or comments, or if you would like to add some definitions or synonyms to this overview.

## Bibliography

### Books

- The nomenclature here is taken from the excellent introduction to Markov chain Monte Carlo (MCMC) methods by Geyer, Charles J (2011), Chapter 1 in Brooks, Steve and Gelman, Andrew and Jones, Galin and Meng, Xiao-Li (2011).
- More advanced topics such as population based MCMC methods are covered in Liang, Faming and Liu, Chuanhai and Carroll, Raymond (2011).
- See Arnaud Doucet and Nando de Freitas and Neil Gordon (2001) for sequential Monte Carlo algorithms.

### Articles

- Walter R. Gilks and Carlo Berzuini (2001)
- Del Moral, Pierre and Doucet, Arnaud and Jasra, Ajay (2006)
- Andrieu, Christophe and Doucet, Arnaud and Holenstein, Roman (2010)
- A. {Doucet} and A. M. {Johansen} (2011)
- Chopin, N. and Jacob, P. E. and Papaspiliopoulos, O. (2012)
- Heng, Jeremy and Bishop, Adrian N. and Deligiannidis, George and Doucet, Arnaud (2020)

### Articles tailored to a phylogenetic audience

- Bouchard-Côté, Alexandre and Sankararaman, Sriram and Jordan, Michael I. (2012)
- Vu Dinh and Aaron E Darling and Frederick A Matsen IV (2018)
- Mathieu Fourment and Brian C. Claywell and Vu Dinh and Connor McCoy and Frederick A. Matsen IV and Aaron E. Darling (2018)

## Necessary definitions

**Elementary updates** are instructions about how to advance a Markov chain so
that it possibly reaches a new state. That is, elementary updates specify how
the chain traverses the state space. Elementary updates cannot be decomposed
into smaller updates.

Elementary updates can be combined to form composite updates, a technique often
referred to as **composition**. We use the word **update** to refer to either an
elementary or a composite update.

Updates can also be executed in random order, a technique often referred to as
**mixture**. Here, the word mixture is used in the sense of mixture models, and
not in the sense of a chain reaching convergence.

The **composition** and **mixture** of elementary updates allows the specification
of all (Is this true?, Please correct me if it is not.) MCMC algorithms
involving a single chain. In particular, Gibbs samplers of all sorts can be
specified using this procedure.

Roughly, a **Markov kernel** is a map describing the probability density (for
continuous spaces) or the probability mass (for discrete spaces) of updating one
state to another.

The **Metropolis-Hasings-Green** algorithm specifies the acceptance probability of
updates so that the stationary distribution of the resulting Markov chain is the
desired posterior distribution.

Many methods to improve convergence of MCMC samplers have been designed. Most
notably, we have methods involving **auxiliary variables** and **population based**
methods running various MCMC samplers in parallel.

## Unnecessary synonyms

- Proposal
- Update.
- Move
- Update.
- Metropolis update
- Update with uniform Markov kernel.
- Metropolis-Hastings update
- Update with arbitrary Markov kernel.

## Unnecessary synonyms and special cases of Metropolis-Hastings-Green MCMC methods

- Fixed scan algorithm
- MCMC sampler involving composition.
- Random scan algorithm
- MCMC sampler involving mixture.
- Random sequence scan algorithm
- MCMC sampler involving composition and mixture.
- Gibbs update
- Update with Metropolis-Hastings ratio of 1.0. That is, Gibbs updates are always accepted. Gibbs updates can be designed using conditional Markov kernels.
- Gibbs sampler
- MCMC sampler in which all of the elementary updates are Gibbs, combined either by composition (fixed scan), by mixture (random scan), or both (random sequence scan).
- Metropolis algorithm
- MCMC sampler in which all of the elementary updates are Metropolis, combined either by composition, mixture, or both (and the same “scan” terminology is used).
- Metropolis-Hastings algorithm
- MCMC sampler in which all of the elementary updates are Metropolis-Hastings, combined either by composition, mixture, or both (and the same “scan” terminology is used).
- Metropolis-within-Gibbs sampler
- The same as the preceding item. This name makes no sense at all since Gibbs is a special case of Metropolis-Hastings.
- Independence Metropolis-Hastings algorithm
- Special case of the Metropolis-Hastings algorithm in which the Markov kernel does not depend on the current state: \(q(x, \cdot)\) does not depend on \(x\).
- Random-walk Metropolis-Hastings algorithm
- Special case of the Metropolis-Hastings algorithm in which the proposal has the form \(x+e\), where \(e\) is stochastically independent of the current state \(x\), so \(q(x, y\) has the form \(f(y-x)\).
- Reversible jump MCMC algorithm
- MCMC sampler including updates between different models possibly having a different set of parameters. However, these updates are in no way special.

## Special cases of auxiliary variable MCMC methods

- Data augmentation.
- Simulated annealing.
- Simulated tempering.

## Special cases of population based MCMC methods

- Sequential Monte Carlo.
- Parallel tempering.
- Metropolic-coupled MCMC (MC3) is Parallel tempering.

## References

A. {Doucet} and A. M. {Johansen} (2011). *{A tutorial on particle filtering and smoothing: fifteen years later}*, Oxford: Oxford University Press.

Andrieu, Christophe and Doucet, Arnaud and Holenstein, Roman (2010). *Particle Markov chain Monte Carlo methods*.

Bouchard-Côté, Alexandre and Sankararaman, Sriram and Jordan, Michael I. (2012). *Phylogenetic inference via sequential monte carlo*.

Chopin, N. and Jacob, P. E. and Papaspiliopoulos, O. (2012). *SMC2: an efficient algorithm for sequential analysis of state space models*.

Del Moral, Pierre and Doucet, Arnaud and Jasra, Ajay (2006). *Sequential Monte Carlo samplers*.

Geyer, Charles J (2011). *{Introduction to Markov Chain Monte Carlo}*, CRC press.

Heng, Jeremy and Bishop, Adrian N. and Deligiannidis, George and Doucet, Arnaud (2020). *Controlled sequential Monte Carlo*.

Liang, Faming and Liu, Chuanhai and Carroll, Raymond (2011). *Advanced Markov chain Monte Carlo methods: learning from past samples*, John Wiley \& Sons.

Mathieu Fourment and Brian C. Claywell and Vu Dinh and Connor McCoy and Frederick A. Matsen IV and Aaron E. Darling (2018). *Effective online bayesian phylogenetics via sequential monte carlo with guided proposals*.

Brooks, Steve and Gelman, Andrew and Jones, Galin and Meng, Xiao-Li (2011). *{Handbook of Markov Chain Monte Carlo}*, CRC press.

Arnaud Doucet and Nando de Freitas and Neil Gordon (2001). *Sequential Monte Carlo Methods in Practice*, Springer New York.

Vu Dinh and Aaron E Darling and Frederick A Matsen IV (2018). *Online Bayesian phylogenetic inference: theoretical foundations via sequential Monte Carlo*.

Walter R. Gilks and Carlo Berzuini (2001). *Following a Moving Target-Monte Carlo Inference for Dynamic Bayesian Models*.