Non Deterministic Approaches

Numerical methods that are known as Monte Carlo methods can be loosely described as statistical simulation methods. A statistical simulation can be defined, in general terms, to be any method that utilizes sequences of random numbers to perform the simulation.

Monte Carlo methods have been used for centuries, but only in the past several decades this technique has gained the status of a full-fledged numerical method capable of addressing the most complex applications. The name "Monte Carlo" was coined by Metropolis (inspired by Ulam's interest in poker) during the Manhattan Project of World War II, because of the similarity of statistical simulation to games of chance, and because the capital of Monaco was a center for gambling and similar pursuits.

Monte Carlo is now used routinely in many diverse fields, from the simulation of complex physical phenomena such as radiation transport in the earth's atmosphere to more common cases, such as the simulation of a Bingo game. The analogy of Monte Carlo methods to games of chance is a good one but, in engineering applications, the "game" is a physical system, a Finite Element model or a black-box function, and the outcome of the game is a solution to some problem. The scientist judges the value of his results on their intrinsic worth, rather than the extrinsic worth of his holdings.

Statistical simulation methods may be contrasted to conventional numerical discretization methods, which typically are applied to ordinary or partial differential equations that describe some underlying physical or mathematical system.

In many applications of Monte Carlo, the physical process is simulated directly, and there is no need to even write down the differential equations that describe the behavior of the system. The only requirement is that the physical (or mathematical) system be described by probability density functions (PDFs).

From now on, we will assume that the behavior of a system can be described by PDFs. Once the PDFs are known, the Monte Carlo simulation can proceed by random sampling from the PDFs. Many simulations are then performed (multiple "trials" or "histories") and the desired result is taken as an average over the number of observations (which may be a single observation or perhaps millions of observations). In many practical applications, one can predict the statistical error (the "variance") in this average result, and hence an estimate of the number of Monte Carlo trials that are needed to achieve a given error.

Assuming that the evolution of the physical system can be described by probability density functions (PDFs), then the Monte Carlo simulation can proceed by sampling from these PDFs, which necessitates a fast and effective way to generate random numbers uniformly distributed on the interval [0,1]. The outcomes of these random samplings, or trials, must be accumulated or tallied in an appropriate manner to produce the desired result, but the essential characteristic of Monte Carlo is the use of random sampling techniques (and perhaps other algebra to manipulate the outcomes) to arrive at a solution of the physical problem. In contrast, a conventional numerical solution approach would start with the mathematical model of the physical system, discretizing the differential equations and then solving a set of algebraic equations for the unknown state of the system.

It should be kept in mind though that this general description of Monte Carlo methods may not directly apply to some applications. It is natural to think that Monte Carlo methods are used to simulate random, or stochastic, processes, since these can be described by PDFs. However, this coupling is actually too restrictive because many Monte Carlo applications have no apparent stochastic content, such as the evaluation of a definite integral or the inversion of a system of linear equations. However, in these cases and others, one can pose the desired solution in terms of PDFs, and while this transformation may seem artificial, this step allows the system to be treated as a stochastic process for the purpose of simulation and hence Monte Carlo methods can be applied to simulate the system.

Therefore, a broad view of the definition of Monte Carlo methods can be taken and can include in the Monte Carlo rubric all methods that involve statistical simulation of some underlying system, whether or not the system represents a real physical process.