Markov Chain Monte Carlo: Theoretical Foundations
Adapted from an appendix of my MS thesis. Markov Chain Monte Carlo Almost as soon as computers were invented, they were used for simulation. Markov chain Monte Carlo (MCMC) was invested as Los Alamos, Metropolis et al (1953) simulated a liquid in equilibrium with its gas phase. Their tour de force was the realization that they did not need to simulate the exact dynamics, they only needed to simulate some Markov chain with the same equilibrium distribution. The Metropolis algorithm was widely used by chemists and physicists, but was not widely known among statisticians until after 1990. Hastings (1970) generalized the Metropolis algorithm, and simulations following his scheme are said to use the Metropolis-Hastings (MH) algorithm [1]. A special case of the MH algorithm was introduced by Geman et al (1984) discussing optimization to find the posterior mode rather than simulation. Algorithms following their scheme are said to use the Gibbs sampler. It took some time for the spatial statistics community to understand that the Gibbs sampler simulated the posterior distribution, thus enabling full Bayesian inference of all kinds. Gelfand et al (1990) made the wider Bayesian community aware of the Gibbs sampler, and then it was rapidly realized that most Bayesian inference could be done using MCMC, whereas very little could be done without MCMC. Green (1995) generalized the MH algorithm as much as it could be generalized [1]. Theoretical Foundations A sequence X 1 , X 2 , … of random elements of some set is a Markov chain if the conditional distribution of X n + 1 given X 1 , … , X n depends on X n only. The set in which the X i take values is called the state space of the Markov chain. A Markov chain has stationary transition probabilities if the conditional distribution of X n + 1 given X n does not depend on n . This is the main kind of Markov chain of interest in MCMC. The joint distribution of a Markov chain is determined by the following [1]. The ma