William Sealy Gosset (13.6.1876 - 16.10.1937)
This birth-and-death process is suffering from labor
pains; it will be the death of me yet. (Student Sayings)
The Monte Carlo method provides approximate solutions to a
variety of mathematical problems by performing statistical sampling experiments on a
computer. The method applies to problems with no probabilistic content as well as to those
with inherent probabilistic structure. Among all numerical methods that rely on N-point
evaluations in M-dimensional space to produce an approximate solution, the Monte Carlo
method has absolute error of estimate that decreases as N superscript -1/2 whereas, in the
absence of exploitable special structure all others have errors that decrease as N
superscript -1/M at best.
History of Monte Carlo method
The method is called after the city in the Monaco
principality, because of a roulette, a simple random number generator. The name and the
systematic development of Monte Carlo methods dates from about 1944.
There are however a number of isolated and undeveloped
instances on much earlier occasions.
For example, in the second half of the nineteenth century a
number of people performed experiments, in which they threw a needle in a haphazard manner
onto a board ruled with parallel straight lines and inferred the value of PI = 3.14…
from observations of the number of intersections between needle and lines. An account of
this playful diversion (indulged in by certain Captain Fox, amongst others, whilst
recovering from wounds incurred in the American Civil War) occurs in a paper Hall (A. HALL
1873. " On an experimental determination of PI"). The author of this WEB page
has developed the software for simulating of this experiment. Try
JAVA implementation of Buffon's needle experiment for the determination of PI.
In 1899 Lord Rayleigh showed that a one-dimensional random
walk without absorbing barriers could provide an approximate solution to a parabolic
In 1931 Kolmogorov showed the relationship between Markov
stochastic processes and certain integro-differential equations.
In early part of the twentieth century, British statistical
schools indulged in a fair amount of unsophisticated Monte Carlo work. Most of this seems
to have been of didactic character and rarely used for research or discovery. Only on a
few rare occasions was the emphasis on original discovery rather than comforting
verification. In 1908 Student (W.S. Gosset) used experimental sampling to help him towards
his discovery of the distribution of the correlation coefficient. In the same year Student
also used sampling to bolster his faith in his so-called t-distribution, which he had
derived by a somewhat shaky and incomplete theoretical analysis.
The real use of Monte Carlo methods as a research tool
stems from work on the atomic bomb during the second world war. This work involved a
direct simulation of the probabilistic problems concerned with random neutron diffusion in
fissile material; but even at an early stage of these investigations, von Neumann and Ulam
refined this particular " Russian roulette" and "splitting" methods.
However, the systematic development of these ideas had to await the work of Harris and
Herman Kahn in 1948. About 1948 Fermi, Metropolis, and Ulam obtained Monte Carlo estimates
for the eigenvalues of Schrodinger equation.
von Neumann (28.12.1903-8.2.1957)
In about 1970, the newly developing theory of computational
complexity began to provide a more precise and persuasive rationale for employing the
Monte Carlo method. The theory identified a class of problems for which the time to
evaluate the exact solution to a problem within the class grows, at least, exponentially
with M. The question to be resolved was whether or not the Monte Carlo method could
estimate the solution to a problem in this intractable class to within a specified
statistical accuracy in time bounded above by a polynomial in M. Numerous examples now
support this contention. Karp (1985) shows this property for estimating reliability in a
planar multiterminal network with randomly failing edges. Dyer (1989) establish it for
estimating the volume of a convex body in M-dimensional Euclidean space. Broder (1986) and
Jerrum and Sinclair (1988) establish the property for estimating the permanent of a matrix
or, equivalently, the number of perfect matchings in a bipartite graph.