Quantum Bayesian Networks

October 28, 2009

The MCMC Revolution

Filed under: Uncategorized — rrtucci @ 7:31 pm

Check out
The MCMC Revolution
Persi Diaconis, Bull. Amer. Math. Soc. 46 (2009), 179-205.

This paper was a lot of fun to read. Though Diaconis is a mathematician, a large fraction of the paper is written at a level understandable by most persons with an undergraduate degree in science or engineering. (Just skip those parts that lie beyond your level). The goal of the paper is to introduce its readers to MCMC (Markov Chain Monte Carlo), and to make them appreciate the enormous usefulness of MCMC in most scientific fields.

Those who read this blog know that the most efficient way of doing MCMC is with a quantum computer. Although the paper is only about s-l-o-w poke classical computers, I still recommend it, so you can see how our dads did things 🙂

The paper motivates the mathematical theory of Markov chains using two cool examples.

(1)(a Metropolis sampling example) A real life detective story. The California prison system asked the Stanford Statistics Department to help it decypher some coded messages that it had intercepted. The messages had been written by a prison inmate using non-standard symbols (in what is called a substitution cypher). A regiment of 2 Stanford students was assigned the task of changing this light bulb. The students used Metropolis sampling with a code “plausibility” measure equal to —censored—. I won’t give away the punchline.

(2)(Monte Carlo integration example) Consider possible placements of $N$ hard discs of radius $r$ inside the unit square. The discs must not overlap and must be completely contained in the unit square. The centers of the $N$ discs are described by a point $x \in R^{2N}$. Let $X(N,r)$ be the subset of $R^{2N}$ containing all possible placements of $N$ discs of radius $r$. The goal is to integrate some function $f:R^{2N} \rightarrow R$ over the region $X(N,r)$.

According to Diaconis

“To someone working in my part of the world, asking about applications of Markov chain Monte Carlo (MCMC) is a little like asking about applications of the quadratic formula. The results are really used in every aspect of scientific inquiry. The following indications are wildly incomplete. I believe you can take any area of science, from hard to social, and find a burgeoning MCMC literature specifically tailored to that area.”

The paper ends with a list of references suggested for further reading, references that describe the application of MCMC in the fields of (1)Chemistry and Physics (2)Biology (3)Statistics (4)Group Theory (5)Computer Science (theory).

Persi Diaconis is a distinguished professor in the Department of Statistics at Stanford University. Since his teens, he has been a skillful performer of magical card tricks. His wife, Susan P. Holmes, is also a distinguished professor in the same Stanford department, where she teaches, you guessed it, applications of MCMC to Biology.