**Instructor's
Notes:**
The term "Monte Carlo Method" is very general. A
Monte Carlo method is a stochastic technique, meaning that it is based
on using random numbers and probability to investigate problems. Monte
Carlo methods are employed in a wide variety of fields including economics,
finance, physics, chemistry, engineering, and even the study of traffic
flows. Each field using Monte Carlo methods may apply them in different
ways, but in essence they are using random numbers to examine some problem
and approximate its outcome. As such Monte Carlo methods give us a way
to model complex systems that are often extremely hard to investigate with
other types of techniques.

"The term 'Monte Carlo' was introduced by von Neumann
and Ulam during World War II, as a code word for the secret work at Los
Alamos; it was suggested by the gambling casinos at the city of Monte Carlo
in Monaco. The Monte Carlo method was then applied to problems related
to the atomic bomb." ( *Simulation and the Monte Carlo Method* by
Reuven Y. Rubinstein, John Wiley & Sons, Inc., New York, 1981, p.11.)
For a brief history of Monte Carlo Methods see http://stud2.tuwien.ac.at/~e9527412/history.html.

It is well known that to approximate the probability
of obtaining a head in coin tossing, we may toss the coin repeatedly, counting
the number of heads obtained, and then divide that number by the total
number of tosses. This simple idea has extensions to more complex experiments.
For a specified event, perform the experiment repeatedly, count the number
of favorable outcomes, and then divide that number by the total number
of times you perform the experiment. We would like to use this idea to
determine the relationship between probability and area by performing a
sequence of simulations.

__Simulation #1.__ Construct a unit square
with vertices (0,0), (1,0), (1,1), and (0,1) along with a smaller square
with vertices (0,0), (1/2,0), (1/2,1/2), and (0,1/2). Now randomly select
and plot points in the unit square and count the number which fall in the
smaller square. Divide the number of points landing in the smaller square
by total number of points selected in the unit square. The result will
approximate the probability of selecting a point in the smaller square.
Of course the probability should be ¼ and it is easy for students
to hypothesize this and so they are not surprised when the result is close
to .25. See Figure 1.

**Figure 1.**
__Simulation #2.__
We graph the same unit square along with the part of a unit circle which
lies in the first quadrant. The simulation then randomly chooses and plots
points in the unit square, continuously counts the number which fall within
the quarter circle, divides by the running total of the number of points
currently plotted, and displays the result as well as 4 times the result.
Because of the first simulation students feel it is reasonable that we
are approximating the area under the quarter circle which of course is
pi/4 and so when we multiply by 4 we obtain an approximation to pi (i.e.
an approximation to the area of a unit circle). See Figure 2.

**
Figure 2.**

Following is an animation which uses
darts to indicate the selection of points in a circle bounded by a square.

**
Throwing Darts.**

The basic idea is expressed
by the following relationship.

Thus if our target (here the circle) had
an unknown area we could estimate the area using

.

__Simulation #3.__ In the
this simulation we again graph the same unit square. This time, however,
we enter a function, which is nonnegative in the first quadrant, and graph
that part of the function, which lies in the unit square. The simulation
then randomly chooses and plots points in the unit square, continuously
counts the number which fall below the graph of the function, divides by
the running total number of points currently plotted, and displays the
result as well as the definite integral of the function from 0 to 1 (This
is computed by the computer algebra capabilities of MathKit). See Figures
3 and 4.

**
Figure 3.**

**
Figure 4.**

All three of these simulations allow the following options.
You may choose the number of random points to be used from 1 to 9999. Because
the slowest part of this process is the graphing of the points, you may
also switch off the plotting of points when you are using large numbers
of random points. **It is clear that if you use more points then your
approximation should be more accurate, but you must also keep in mind that
this process is stochastic and so you need to perform the simulation several
times to get a sense of what is occurring. **It is also interesting to
note that as you increase the number of points used in the simulation by
a factor of 10 the accuracy of the result generally only improves by a
factor of about 3.
Of course what we have built is known as a Monte
Carlo integrator.

Clearly, in these simulations the graphics is fluff
(but nice fluff). The same simulations could be created in almost any programming
environment (without the graphics) but would your students be as easily
convinced of the results?

To create the first simulation you need to choose
pairs of numbers from a stream of uniformly distributed random numbers
from 0 to 1. The first number is the x coordinate and the second is the
y coordinate. Choose N pairs and test them against the condition
and .
If K pairs pass the test then the area approximation is K/N.

Similarly, for the second simulation you need to
choose pairs of numbers from a stream of uniformly distributed random numbers
from 0 to 1. The first number is the x coordinate and the second is the
y coordinate. Choose N pairs and test them against the condition .
If K pairs pass the test then the area approximation is K/N so 4K/N should
be an approximation for pi.

For the third simulation you also need to choose
pairs of numbers from a stream of uniformly distributed random numbers
from 0 to 1. The first number is the x coordinate and the second is the
y coordinate. Choose N pairs and test them against the condition .
If K pairs pass the test then the area approximation is K/N.

It is clear that we can extend this idea beyond nonnegative
functions on the unit square. We need to box the function in a rectangle,
say and .
Next choose pairs of numbers from a stream of uniformly distributed random
numbers from 0 to 1. Multiply the first number by b-a and add a to obtain
numbers uniformly distributed between a and b. Similarly multiply the second
number by d-c and add c to obtain numbers uniformly distributed between
c and d. The first number is the x coordinate and the second is the y coordinate.
Choose N pairs and test them against the condition .
If K pairs pass the test then the probability that they lie below the curve
is K/N and so for nonnegative functions the area under the curve is (K/N)(b-a)(d-c).

This process may be modified for functions which
fail to be nonnegative (by performing translations). It can also be used
to approximate volumes under surfaces in higher dimensions. In fact this
technique was used at Los Alamos during the very early days of computing
to solve some very difficult differential equations in higher dimensions.

Although we use these simulations in a Modeling and
Simulation course they are appropriate for any course where one is discussing
probability.

A MathKit program to generate Figures 1 - 3 can be
downloaded by clicking on Mc_area.

__Related Materials:__

For courses where a detailed foundation
is needed for the Monte Carlo integrator, click on foundation
for a pdf file which contains a development using expected value.

A short bibliography for other introductory
examples of using Monte Carlo techniques is available in a pdf file,
bibliography. A number of these articles have applications which are
suitable for precalculus, liberal arts courses, and even high school courses.
Citations to several java applets are included. There is a very nice one
as available at exploremath.com.

A **MATLAB** routine for area approximation
is available for down loading; click on montecarlo.m
. This an interactive routine similar to that described above for MathKit.
To see a picture of the result of an experiment click on MATLAB
screen.

**Credits**:
This demo was submitted by

Anthony
Berard

Department of Mathematics

Kings College

and is included in **Demos
with Positive Impact** with his permission.