The Monte Carlo approach is a radically new approach to problem solving first developed in the 1940’s. Someone has said that the Monte Carlo method may be the most commonly used mathematical technique which wasn’t familiar to Gauss. When faced with a problem that is too difficult to solve exactly, the Monte Carlo approach says to create a random process that is likely to give a good approximation to the desired result. This approach has become so widely adopted that it is difficult to appreciate how groundbreaking it was a few decades ago.
Monte Carlo methods are often either omitted from the undergraduate curriculum or are presented in a misleading way. Perhaps the application most likely presented to undergraduates would be numerical integration. Imagine the graph of a function of many variables sitting inside a high dimensional box. The integral of the function is the volume under the graph, and so one can approximate the integral by generating random points and counting what proportion of points fall below the surface. There is some truth to this. Monte Carlo methods are the only practical way to estimate many high dimensional integrals, and in principle the dart-throwing technique would work. However, numerical integration is almost never done in such a crude way. Such examples may do more harm than good because they imply that Monte Carlo methods are trivial. Monte Carlo methods are conceptually simple, but they do require some sophistication to use effectively.
To see why the “just throw darts at it” approach might not work, imagine estimating the volume of a 40-dimensional sphere. Place the sphere in a cube of the same diameter and count the proportion of random points that land inside the sphere. This proportion will converge to the volume of the sphere. However, this method is completely impractical without some refinement. The probability of a single point landing inside the sphere is 3.44 × 10-15. (The volume of a unit sphere of dimension 2n is πn/Γ(n) and so the proportion of the unit cube taken up by the sphere decreases rapidly as n increases.) To estimate the volume to three decimal places, you would need about 106 to land inside the sphere, which means you would have to throw on the order of 1021 darts. Throwing a billion simulated darts a second, this would take over 30,000 years. High dimensional volumes are often estimated using Monte Carlo techniques, but not by naively throwing darts at a box. In practice, darts have to be thrown according to some non-uniform distribution that assures that a sizeable proportion of the darts land inside the target.
Monte Carlo methods are very commonly used in applications. Mathematics students should have a practical introduction to such methods, but introductions at an undergraduate level are hard to find. Explorations in Monte Carlo Methods by Ronald Shonkwiler and Franklin Mendivil is an undergraduate text that is both practical and accessible. The book has minimal prerequisites. It assumes the reader is comfortable with calculus and matrices, but it does not assume much background in probability or statistics. And although the book assumes little background, it covers advanced topics such as Markov chain Monte Carlo (MCMC) and simulated annealing.
Explorations would make a good text book and would also be suitable for independent study. It makes ideas accessible at a sophomore level that are normally covered in graduate or advanced undergraduate texts. The book leads up to big ideas by a sequence of simple motivating examples. For example, before introducing acceptance-rejection methods for generating random numbers, it first explains how to generate random samples with probability of success 1/3 by tossing a fair coin. It gives numerous applications of Monte Carlo methods including applications in electrical engineering, finance, optimization, and statistical mechanics. Each chapter has numerous exercises and the book concludes with an appendix listing several ideas for student projects applying Monte Carlo methods.
John D. Cook is a research statistician at M. D. Anderson Cancer Center and blogs daily at The Endeavour.