Module

for

Monte Carlo Pi

 

Background

    We start the familiar example of finding the area of a circle.  Figure 1 below shows a circle with radius [Graphics:Images/MonteCarloPiMod_gr_1.gif] inscribed within a square. The area of the circle is  [Graphics:Images/MonteCarloPiMod_gr_2.gif],  and the area of the square is [Graphics:Images/MonteCarloPiMod_gr_3.gif].  The ratio of the area of the circle to the area of the square is   
    
        [Graphics:Images/MonteCarloPiMod_gr_4.gif]  

        

[Graphics:Images/MonteCarloPiMod_gr_5.gif]

  
        Figure 1.  [Graphics:Images/MonteCarloPiMod_gr_6.gif]  


    If we could compute ratio, then we could multiple it by four to obtain the value [Graphics:Images/MonteCarloPiMod_gr_7.gif].  One particularly simple way to do this is to pick lattice points in the square and count how many of them lie inside the circle, see Figure 2.  Suppose for example that the points [Graphics:Images/MonteCarloPiMod_gr_8.gif] are selected, then there are 812 points inside the circle and 212 points outside the circle and the percentage of points inside the circle is  [Graphics:Images/MonteCarloPiMod_gr_9.gif].  Then the area of the circle is approximated with the following calculation  
    
    [Graphics:Images/MonteCarloPiMod_gr_10.gif]  

        

[Graphics:Images/MonteCarloPiMod_gr_11.gif]

    
        Figure 2.  [Graphics:Images/MonteCarloPiMod_gr_12.gif]  

 

Monte Carlo Method for [Graphics:Images/MonteCarloPiMod_gr_13.gif]

    Monte Carlo methods can be thought of as statistical simulation methods that utilize a sequences of random numbers to perform the simulation.  The name "Monte Carlo'' was coined by Nicholas Constantine Metropolis (1915-1999) and inspired by Stanslaw Ulam (1909-1986), because of the similarity of statistical simulation to games of chance, and because Monte Carlo is a center for gambling and games of chance.  In a typical process one compute the number of points in a set A that lies inside box R.  The ratio of the number of points that fall inside A to the total number of points tried is equal to the ratio of the two areas (or volume in 3 dimensions).  The accuracy of the ratio [Graphics:Images/MonteCarloPiMod_gr_14.gif] depends on the number of points used, with more points leading to a more accurate value.

    A simple Monte Carlo simulation to approximate the value of  [Graphics:Images/MonteCarloPiMod_gr_15.gif]  could involve randomly selecting points  [Graphics:Images/MonteCarloPiMod_gr_16.gif]  in the unit square and determining the ratio  [Graphics:Images/MonteCarloPiMod_gr_17.gif],  where [Graphics:Images/MonteCarloPiMod_gr_18.gif] is number of points that satisfy  [Graphics:Images/MonteCarloPiMod_gr_19.gif].  In a typical simulation of sample size [Graphics:Images/MonteCarloPiMod_gr_20.gif] there were [Graphics:Images/MonteCarloPiMod_gr_21.gif] points satisfying  [Graphics:Images/MonteCarloPiMod_gr_22.gif],  shown in Figure 3.  Using this data, we obtain
    
    [Graphics:Images/MonteCarloPiMod_gr_23.gif]  and   [Graphics:Images/MonteCarloPiMod_gr_24.gif]  
    
        

[Graphics:Images/MonteCarloPiMod_gr_25.gif]

  
        Figure 3.  [Graphics:Images/MonteCarloPiMod_gr_26.gif]   

    Every time a Monte Carlo simulation is made using the same sample size [Graphics:Images/MonteCarloPiMod_gr_27.gif] it will come up with a slightly different value.  The values converge very slowly of the order  [Graphics:Images/MonteCarloPiMod_gr_28.gif].  This property is a consequence of the Central Limit Theorem.

Proof  Monte Carlo Pi  

 

Remark.  Another interesting simulation for approximating  [Graphics:Images/MonteCarloPiMod_gr_29.gif]  is known as Buffon's Needle problem.  The reader can find many references to it in books, articles and on the internet.  

 

Computer Programs  Monte Carlo Pi

Mathematica Subroutine (Monte Carlo Pi).

[Graphics:Images/MonteCarloPiMod_gr_30.gif]

Example 1.  Use Monte Carlo simulation to approximate the number  [Graphics:Images/MonteCarloPiMod_gr_31.gif].
Solution 1.

 

Area Under a Curve

    Monte Carlo simulation can be used to approximate the area  [Graphics:Images/MonteCarloPiMod_gr_49.gif] under a curve  [Graphics:Images/MonteCarloPiMod_gr_50.gif]  for  [Graphics:Images/MonteCarloPiMod_gr_51.gif].  First, we must determine the rectangular box [Graphics:Images/MonteCarloPiMod_gr_52.gif] containing [Graphics:Images/MonteCarloPiMod_gr_53.gif] as follows.
    
        [Graphics:Images/MonteCarloPiMod_gr_54.gif]  where  [Graphics:Images/MonteCarloPiMod_gr_55.gif].  
        
Second, randomly pick points  [Graphics:Images/MonteCarloPiMod_gr_56.gif]  in [Graphics:Images/MonteCarloPiMod_gr_57.gif], where [Graphics:Images/MonteCarloPiMod_gr_58.gif] are chosen from independent uniformly distributed random variables over  [Graphics:Images/MonteCarloPiMod_gr_59.gif], respectively.   Third, calculate the ratio [Graphics:Images/MonteCarloPiMod_gr_60.gif] as follows:

         [Graphics:Images/MonteCarloPiMod_gr_61.gif], where [Graphics:Images/MonteCarloPiMod_gr_62.gif] is number of points that lie in  [Graphics:Images/MonteCarloPiMod_gr_63.gif].  

The area is computed using the approximation,  [Graphics:Images/MonteCarloPiMod_gr_64.gif],  and we can use the formula  

        [Graphics:Images/MonteCarloPiMod_gr_65.gif].     
    
An "estimate" for the accuracy of the above computation is
    
        [Graphics:Images/MonteCarloPiMod_gr_66.gif].  

 

Algorithm Monte Carlo Simulation.  Given that   [Graphics:Images/MonteCarloPiMod_gr_67.gif]  for  [Graphics:Images/MonteCarloPiMod_gr_68.gif].  Use Monte Carlo simulation to approximate the integral  

        [Graphics:Images/MonteCarloPiMod_gr_69.gif].  

Mathematica Subroutine (Monte Carlo Simulation).

[Graphics:Images/MonteCarloPiMod_gr_70.gif]

Caveat.  The above subroutine is for pedagogical purposes.  The standard implementation of Monte Carlo integration is done by selecting points only in the domain of the function, for a one dimensional integral we would use random numbers to select points [Graphics:Images/MonteCarloPiMod_gr_71.gif] in the interval [Graphics:Images/MonteCarloPiMod_gr_72.gif] and then use the approximation

        [Graphics:Images/MonteCarloPiMod_gr_73.gif].

This idea will be developed in the module Monte Carlo integration.

 

Example 2.  Use Monte Carlo simulation to approximate the integral  [Graphics:Images/MonteCarloPiMod_gr_74.gif]
Solution 2.

 

Example 3.  Use Monte Carlo simulation to approximate the integral  [Graphics:Images/MonteCarloPiMod_gr_91.gif]
Solution 3.

 

Example 4.  Use Monte Carlo simulation to approximate the integral  [Graphics:Images/MonteCarloPiMod_gr_108.gif]
Solution 4.

 

Question.  Which of the above three examples will give better results if the goal is to obtain a numerical approximation of  [Graphics:Images/MonteCarloPiMod_gr_125.gif]
Answer.

 

Example 5.  Use Monte Carlo simulation to approximate the integral  [Graphics:Images/MonteCarloPiMod_gr_137.gif].  
Solution 5.

 

Area of a region defined by inequalities.

    Monte Carlo simulation can be used to approximate the area of a region defined by a set of inequalities or constraints.

Mathematica Subroutine (Monte Carlo Simulation).

[Graphics:Images/MonteCarloPiMod_gr_158.gif]

Example 6.  Use Monte Carlo simulation to approximate the area of the cardioid defined by the constraint

        [Graphics:Images/MonteCarloPiMod_gr_159.gif].

Solution 6.

 

Example 7.  Use Monte Carlo simulation to approximate the area of the region defined by the constraints

        [Graphics:Images/MonteCarloPiMod_gr_180.gif]  

Solution 7.

 

Research Experience for Undergraduates

Monte Carlo Pi  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Monte Carlo Pi

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2005