Monte Carlo Area Simulations

  • Objective
  • Level
  • Prerequisites
  • Platform
  • Instructor's Notes
  • Credits
  • The local weather forecaster 
    using random selection.
     
    Objective: To illustrate the relationship between probability and area.

    Level: Courses which include introductory probability, simulation topics, or numerical approximation

    Prerequisites: Basic probability concepts.

    Platform: Any computing environment, which supports random number generation. Figures displayed below were generated using MathKit. (Other platforms are referenced.)

    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.


     

    DRH 3/20/01          DRH  Last updated 1/30/2005

    Since 3/1/2002