Area Estimates
by Monte Carlo Simulation
|
|
Objective:
To
estimate the area of a circle or triangle using a probability experiment
employing the Monte Carlo technique. We also indicate how to use our approach
to estimate the area of a polygonal region. (For a general description
of the Monte Carlo technique go to the
Elementary
Probability Demo Collection.)
Level: High
school, precalculus, or probability courses for math majors.
Prerequisites:
Basic
probability concepts; knowledge of equally likely chance and the chance
of winning a lottery.
Platform: A
calculator or computer which has a function that
generates random numbers or alternatively a phone book. Several MATLAB
routines are used for illustrations of the technique.
Instructor's
Notes:
We start with a typical problem that can be solved
by geometry or estimated by Monte Carlo simulation experiments. We extend
the solution of this basic problem to the estimation of the area of other
geometric figures.
Find the probability p of selecting a
point on or in the interior of a circle of radius 1 which is inscribed
in a square with side 2. (Assume that the circle is centered at the origin.)
To use Monte Carlo simulation we use a random number
generator to obtain ordered pairs (x, y) where -1 
x 1 and -1
y 1. If 
then (x, y) is in the circle. When a large number of pairs (x ,y) are chosen,
then the ratio
approximates the probability p. It follows that
the area of the circle is approximately  .
An interesting procedure for generating
the random numbers is to use a telephone directory. The last two, three,
or four digits of the telephone numbers in any column of any page can be
used as a coordinate of a point in the square. (The first three digits
of a telephone number represent a locality and are not random.) Using the
last four digits a decimal between 1 and -1 is encoded as follows:
If the leading digit is even,
then the decimal is taken to be positive; otherwise it is negative. The
remaining three digits are used to form a decimal of the style  .
Having generated an x-coordinate as described
above, repeat the procedure on the phone number in the adjacent column
of the page to obtain the corresponding y-coordinate. Naturally we could
use calculators or computers to generate the pairs (x, y). However, the
phone book generation enhances the hands-on aspect and seems to stimulate
a real involvement with the overall process.
This experiment works very well using collaborative
groups. Each group selects a page from the telephone directory and two
adjacent columns. Students have enjoyed this approach and there is an opportunity
for this to evolve into team projects. Such extensions may involve areas
of polygonal figures, going to 3-dimensions (a sphere within a cube), or
going further to n-dimensions (an n-ball in an n-dimensional hypercube).
The animation in Figure 1 illustrates the
probability computation described above. This animation was created using
a MATLAB routine which can be downloaded by clicking on
montecirc.ZIP
. (This routine lets the user select the number of random trials to use
for an experiment.) Table 1 presents the approximations for a set of such
experiments.
Figure 1.
Table 1.
A triangle is a familiar polygonal region whose
area can be approximated by a Monte Carlo process. The animation in Figure
2 illustrates such an approximation. This
animation was created using a MATLAB routine which can be downloaded
by clicking on montetri.ZIP . (This routine
lets the user select the vertices of the triangle either by entering three
distinct ordered pairs or using a mouse generate the triangle. In addition
the number of random trials to use for an experiment can be specified.)
The approximation generated in the animation is 13 square units, which
is actually quite close to the exact area, 13.5. The triangle shown in
Figure 2 has vertices A(-1,3) B(4,1), and C(1,-2). Other experiments with
this triangle need not produce as accurate an approximation even if we
increase the number of trials. Table 2 presents the approximations
for such a set of such experiments.
Figure 2.
Table 2.
From the data in Table 2 we infer that
in order to have confidence in the approximation generated from a Monte
Carlo simulation, a large number of trials are needed. We ran 100 experiments
for the triangle in the animation in Figure 2 using k = 1000. All estimations
were between 8.1 and 12.6 with an average of 10.636, yet the exact area
is 13.5. A natural question is, how many experiments
should be used and how many trials should be used? If you get this
question, your students have tuned in to this modeling problem and are
ready for more ideas in probability theory.
Another question arises when you compare the circle
simulation with the triangle simulation. Since we know that (x, y) where
-1 x
1 and
-1
y 1 is in the circle
provided ,
how was it determined whether (x, y) where -5
x 5 and -5
y 5 is in the triangle
ABC?
We don't have an equation for the triangle (in usual
sense), so how do test the coordinates (x ,y)? For beginning classes this
may be difficult to answer, but it is a good question for students to write
about. It is possible to relate the situation to inequalities (click on
inequalitydemo
for foundational material) or linear algebra with systems of equations
and parametric representations of lines. For advanced classes the notion
of the convex hull of a set a points can be used. In fact for polygons,
the notion of the convex hull is very useful for determining whether or
not (x, y) is within the polygon.
Other resources.
A nice
web-based Monte Carlo simulation for approximating the area of a circle
is
available at
http://www.explorelearning.com/
Use
the key phrase geometric probability in the search feature to find a gizmo
related to this demo. On
this site students are able generalize the area example
by changing the size of
the circle and a surrounding rectangle.
For a more general setting for area estimation under a curve go
to
Monte Carlo Demo.
Credits:
A portion of this demo was adapted from the following work.
Regina Brunner, "Numbers, Please! The Telephone
Directory and Probability", The Mathematics Teacher, Vol. 90, No.
9, Dec. 1997, pp. 704 -705.
and we appreciate the cooperation of
Regina
Brunner
Assistant to the Provost for Research
and Planning
Kutztown University
in its development.
We also acknowledge contributions by Un
Jung Sin , student at Temple University. The MATLAB routines were written
by David R. Hill.
|
|
