The Monte Carlo Method (01TSGKG)

Ph.D. School
of the
Polytechnic University of Torino

Fausto Rossi

Department of Applied Science and Technology

Polytechnic University of Torino

Year 2023/24 — Part 1

Introduction: What is Monte Carlo?

Outline:

→ The name of the game

→ Historical background
→ Two different points of view about Monte Carlo

Bibliography:

→ J.M. Hammersley and D.C. Handscomb, Monte Carlo

Methods (Methuen, London, 1964)
→ R.Y. Rubinstein, Simulation and the Monte Carlo Method
(John Wiley & Sons, New York, 1981)
→ M.H. Kalos and P.A. Whitlock, Monte Carlo Methods (John
Wiley & Sons, New York, 1986)
The name of the game
The name “Monte Carlo”:

was introduced first in Los Alamos by the scientists of the

“Manhattan project” in the 1940s
The essence of the method:
→ The invention of games of chance whose behavior and
outcome may be used to study physical phenomena of interest
Link with computers:
→ There is in principle no essential link with computers
→ However, the effectiveness of numerical or simulated
“gambling” is enormously enhanced by the availability
of modern computers
A long gestation:
→ For a relatively long time:
a large part of the scientific community claimed that
Monte Carlo will never produce more than rough estimates
Historical background

The earliest document

→ The earliest documented use of “random sampling”

to solve an integral:
is that of Comte de Buffon

G. Comte de Buffon, “Essai d’arithmétique morale”, Supplément à l’Historie Naturelle, Vol. 4 (1777)

In 1777 he described the following experiment:

A needle of length L is thrown at random onto an horizontal
plane ruled with straight lines a distance d (d > L) apart
What is the probability P that the needle will intersect
one of these lines?
Historical background

The earliest document

Comte de Buffon:
→ repeated this experiment many times to determine P
→ evaluated P analytically as well

2L
P=
πd

Such an experiment:
may be easily translated into a computer simulation
Computer simulation of the
Comte de Buffon’s experiment

L
in this simulation: d = 45 , P= 2L
πd ' .51
After the Comte de Buffon’s experiment

→ Some years later, Laplace suggested to use this idea

to evaluate π
→ Also Lord Kelvin used a sort of “random sampling” in order
to estimate some integrals of the kinetic theory:
it consisted of drawing numbered pieces of paper from a bowl
→ In the 1930s, Enrico Fermi made some numerical experiments
that would now be called Monte Carlo calculations:
he studied the behavior of the newly discovered neutron
→ During the Second World War the bringing together of such
people as Von Neumann, Fermi, Ulam, and Metropolis and
more recently the development of modern digital computers:
gave a strong impetus to the advancement of Monte Carlo
Cross-disciplinary character of the Monte Carlo method:
a few recent publications
→ J. Spanier and E.M. Gelbard, Monte Carlo Principles and Neutron
Transport Problems (Dover Publications, 2008)
→ D. Sorensen and D. Gianola, Likelihood, Bayesian and MCMC Methods in
Quantitative Genetics (Springer, 2007)
→ S.M. Lynch, Introduction to Applied Bayesian Statistics and Estimation
for Social Scientists (Springer, 2007)
→ J.B. Anderson, Quantum Monte Carlo: Origins, Development,
Applications (Oxford University Press, 2007)
→ B.F. Manly, Randomization, Bootstrap and Monte Carlo Methods in
Biology (Chapman & Hall, 2006)
→ G. Winkler, Image Analysis, Random Fields and Markov Chain Monte
Carlo Methods: A Mathematical Introduction (Springer, 2006)
→ J. Mun, Modeling Risk: Applying Monte Carlo Simulation, Real Options
Analysis, Forecasting, and Optimization Techniques (Wiley, 2006)
→ D.P. Landau and K. Binder, A Guide to Monte Carlo Simulations in
Statistical Physics (Cambridge University Press, 2005)
Cross-disciplinary character of the Monte Carlo method:
a few recent publications

→ M. Dapor, Electron-Beam Interactions with Solids: Application of the

Monte Carlo Method to Electron Scattering Problems (Springer, 2004)
→ P. Glasserman, Monte Carlo Methods in Financial Engineering (Springer,
2003)
→ J.C. Spall, Introduction to Stochastic Search and Optimization (Wiley,
2003)
→ B. Lapeyre, Introduction to Monte-Carlo Methods for Transport and
Diffusion Equations (Oxford University Press, 2003)
→ K. Binder and D.W. Heermann, Monte Carlo Simulation in Statistical
Physics, 4th Edition (Springer, 2002)
→ S.A. Dupree and S.K. Fraley, A Monte Carlo Primer: A Practical
Approach to Radiation Transport (Springer, 2001)
→ A. Dubi, Monte Carlo Applications in Systems Engineering (Wiley, 2000)
Two different points of view about Monte Carlo

The mathematical point of view

→ The Monte Carlo method may be regarded as a stochastic

approach to the evaluation of sums and integrals:
a deterministic result is obtained via a “game of chance”

The physical point of view

→ The Monte Carlo method may be regarded as a

direct simulation of physical phenomena:
it allows the simulation of natural stochastic processes
As we shall see:
the above subdivision is somehow artificial and arbitrary
The mathematical point of view
Example of a Monte Carlo quadrature
→ Let us consider a circle and its circumscribed square
→ The ratio of the area of the circle
to the area of the square is π4
The mathematical point of view

Example of a Monte Carlo quadrature

→ Placing at random points in the square:

it is plausible that a fraction π4 of the points
would lie inside the circle
π
→ Therefore one can measure 4:
e.g., by putting a round cake pan inside a square cake pan
and collecting rain in both

As alternative strategy:
one may also “simulate” such an experiment
The mathematical point of view
A numerical example

N in 785, 713 π
e= tot
= = 0.785713 ' = 0.785375 . . .
N 1, 000, 000 4
The physical point of view

Estimation of the chance of winning at solitaire

The present example of Monte Carlo simulation:

is cited by S. Ulam in his autobiography
S. Ulam, Adventures of a Mathematician (Charles Scribner’s Sons, New York, 1976), pp. 196

→ Let us suppose that:

the deck is perfectly shuffled before laying out the cards
→ After choosing a particular strategy for placing
one pile of cards on another:
the problem is a straightforward one in
elementary probability theory
however it is a tedious one
The physical point of view

Estimation of the chance of winning at solitaire:

its computer simulation

→ It is easy
to “randomize” lists representing the 52 cards of a deck
and
to simulate the game to completion

This may be regarded as:

a faithful simulation of a real random process