«
»

A History of Markov Chain Monte Carlo

Sep 17th, 2008| 02:11 pm | Posted by hlee

I’ve been joking about the astronomers’ fashion in writing Markov chain Monte Carlo (MCMC). Frequently, MCMC was represented by Monte Carlo Markov Chain in astronomical journals. I was curious about the history of this new creation. Overall, I thought it would be worth to learn more about the history of MCMC and this paper was up in arxiv:

[stat.CO:0808.2902] A History of Markov Chain Monte Carlo–Subjective Recollections from Incomplete Data– by C. Robert and G. Casella
Abstract: In this note we attempt to trace the history and development of Markov chain Monte Carlo (MCMC) from its early inception in the late 1940′s through its use today. We see how the earlier stages of the Monte Carlo (MC, not MCMC) research have led to the algorithms currently in use. More importantly, we see how the development of this methodology has not only changed our solutions to problems, but has changed the way we think about problems.

Here is the year list of monumental advances in the MCMC history,

  • 1946: ENIAC
  • late 1940′s: inception along with Monte Carlo methods.
  • 1953: Metropolis algorithm published in Journal of Chemical Physics (Metropolis et al.)
  • 1970: Hastings algorithms in Biometrika (Hastrings)
  • 1974: Gibbs sampler and Hammersley-Clifford theorem paper by Besag and its discussion by Hammersley in JRSSS B
  • 1977: EM algorithm in JRSSS B (Dempster et al)
  • 1983: Simulated Annealing algorithm (Kirkpatrick et al.)
  • 1984: Gibbs sampling in IEEE Trans. Pattern Anal. Mach. Intell. (Geman and Geman, this paper is responsible for the name)
  • 1987: data augmentation in JASA (Tanner and Wong)
  • 1980s: image analysis and spatial statistics enjoyed MCMC algorithms, not popular with others due to the lack of computing power
  • 1990: seminal paper by Gelfand and Smith in JSAS
  • 1991: BUGS was presented at the Valencia meeting
  • 1992: introductory paper by Casella and Georgy
  • 1994: influential MCMC theory paper by Tierney in Ann. Stat.
  • 1995: reversible jump algorithm in Biometrika (Green)
  • mid 1990′s: boom of MCMC due to particle filters, reversible jump and perfect sampling (second-generation of MCMC revolution)

and a nice quote from conclusion.

MCMC changed out emphasis from “closed form” solutions to algorithms, expanded our immpact to solving “real” applied problems, expanded our impact to improving numerical algorithms using statistical ideas, and led us into a world where “exact” now means “simulated”!

If you consider applying MCMC methods in your data analysis, references listed in Robert and Casella serve as a good starting point.

Tags: , , , , , , , ,
Category: Algorithms, arXiv, Bad AstroStat, Bayesian, Cross-Cultural, Data Processing, Imaging, MC, MCMC, Methods, Quotes, Stat  |  Comment (RSS)  |  Trackback
2 Comments
  1. Robin Morris:

    My experience is that “Monte Carlo Markov Chain” is often a result of writing by non-native English speakers –MCMC in French would be expanded as “Monte Carlo par Chaines de Markov” (or somesuch), leading to Monte Carlo Markov Chain when (incorrectly) tranlated into English. At least that was my experience when I was a postdoc in France many years ago.

    09-19-2008, 3:55 pm
  2. hlee:

    I tremendously appreciate your comment, a piece of history I would never know.

    09-19-2008, 4:04 pm
Leave a comment