Computational Techniques in Theoretical Physics
Section 8
What is Monte Carlo?
Monte Carlo Methods in Condensed Matter Physics and other disciplines

Monte Carlo method is one of the most widely used numerical methods in physics---from quantum field theory to condensed matter physics. It is also widely used in other disciplines.

Examples of applications:


What Is Monte Carlo?


The name  Monte Carlo was applied to a class of mathematical methods first by scientists working on the development of nuclear weapons in Los Alamos in the 1940s. The essence of the method is the invention of games of chance whose behavior and outcome can be used to study some interesting phenomena. While there is no essential link to computers, the effectiveness of numerical or simulated gambling as a serious scientific pursuit is enormously enhanced by the availability of modern digital computers.

It is interesting, and may strike some as remarkable, that carrying out games of chance or random sampling will produce anything worthwhile. Indeed some authors have claimed that Monte Carlo will never be a method of choice for other than rough estimates of numerical quantities.

Before asserting the contrary, we shall give a few examples of what we mean and do not mean by Monte Carlo calculations.

Consider a circle and its circumscribed square. The ratio of the area of the circle to the area of the square is pi/4. It is plausible that if points were placed at random in the square, a fraction of pi/4 would also lie inside the circle. If that is true (and we shall prove later that in a certain sense it is), then one could measure pi/4 by putting a round cake pan with diameter L inside a square cake pan with side L and collecting rain in both. It is also possible to program a computer to generate random pairs of Cartesian coordinates to represent random points in the square and count the fraction that lie in the circle. This fraction as determined from many experiments should be close to pi/4, and the fraction would be called an estimate for pi/4. In 1,000,000 experiments it is very likely (95\% chance) that the number of points inside the circle would range between 784,600 and 786,200, yielding estimates of pi/4 that are between 0.7846 and 0.7862, compared with the true value of 0.785398...

The example illustrates that random sampling may be used to solve a mathematical problem, in this case, evaluation of a definite integral,

I = int 0 to1 int 0 to sqrt{1-x2}   dx, dy

The answers obtained are statistical in nature and subject to the laws of chance. This aspect of Monte Carlo is a drawback, but not a fatal one since one can determine how accurate the answer is, and obtain a more accurate answer, if needed, by conducting more experiments. Sometimes, in spite of the random character of the answer, it is the most accurate answer that can be obtained for a given investment of computer times. The determination of the value of pi can of course be done faster and more accurately by non-Monte Carlo methods. In many dimensions, however, Monte Carlo methods are often the only effective means of evaluating integrals.

A second and complementary example of a Monte Carlo calculation is one that S.~Ulam cited in his autobiography. Suppose one wished to estimate the chances of winning at solitaire, assuming the deck is perfectly shuffled before laying out the cards. Once we have chosen a particular strategy for placing one pile of cards on another, the problem is a straightforward one in elementary probability theory. It is also a very tedious one. It would not be difficult to program a computer to randomize lists representing the 52 cards of a deck, prepare lists representing the different piles, and then simulate the playing of the game to completion. Observation over many repetitions would lead to a Monte Carlo estimate of the chance of success. This method would in fact be the easiest way of making any such estimate. We can regard the computer gambling as a faithful simulation of the real random process, namely, the card shuffling.

Random numbers are used in many ways associated with computers nowadays. These include, for example, computer games and generation of synthetic data for testing. These are of course interesting, but not what we consider Monte Carlo, since they do not produce numerical results.

Definition of  Monte Carlo method

A method that involves deliberate use of random numbers in a calculation that has the structure of a stochastic process.

Stochastic process:

A sequence of states whose evolution is determined by random events. In a computer, these are generated by random numbers.

Distinction between simulation and Monte Carlo

Simulation is a rather direct transcription into computing terms of a natural stochastic process (as in the example of solitaire).

Monte Carlo, by contrast, is the solution by probabilistic methods of nonprobabilistic problems (as in the example of pi computation).

The distinction is somewhat useful, but often impossible to maintain. The emission of radiation from atoms and its interaction with matter is an example of a natural stochastic process since each event is to some degree unpredictable. It lends itself very well to a rather straightforward stochastic simulation. But the average behavior of such radiation can also be described by mathematical equations whose numerical solution can be obtained using Monte Carlo methods. Indeed the same computer code can be viewed simultaneously as a ``natural simulation'' or as a solution of the equations by random sampling. As we shall also see, the latter point of view is essential in formulating efficient schemes. The main point we wish to stress here is that the same techniques yield directly both powerful and expressive simulation and powerful and efficient numerical methods for a wide class of problems. We should like to return to the issue of whether Monte Carlo calculations are in fact worth carrying out. This can be answered in a pragmatic way: many people do them and they have become an accepted part of scientific practice in many fields. The reasons do not always depend on pure computational economy. As in our solitaire example, convenience, ease, directness, and expressiveness of the method are important assets, increasingly so as pure computational power becomes cheaper. In addition, as asserted in discussing pi, Monte Carlo methods are in fact computationally effective, compared with deterministic methods when treating many dimensional problems. That is partly why their use is so widespread in operations research, in radiation transport (where problems in up to seven dimensions must be dealt with), and especially in statistical physics and chemistry (where systems of hundreds or thousands of particles can now be treated quite routinely). An exciting development of the past few years is the use of Monte Carlo methods to evaluate path integrals associated with field theories as in quantum chromodynamics.