Monte Carlo Pi

Background

    We start the familiar example of finding the area of a circle.  Figure 1 below shows a circle with radius inscribed within a square. The area of the circle is  ,  and the area of the square is .  The ratio of the area of the circle to the area of the square is   
    
          

        

  
        Figure 1.    

    If we could compute ratio, then we could multiple it by four to obtain the value .  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 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  .  Then the area of the circle is approximated with the following calculation  
    
      

        

    
        Figure 2.    

Monte Carlo Method for

    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 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    could involve randomly selecting points    in the unit square and determining the ratio  ,  where is number of points that satisfy  .  In a typical simulation of sample size there were points satisfying  ,  shown in Figure 3.  Using this data, we obtain
    
      and     
    
        

  
        Figure 3.     

    Every time a Monte Carlo simulation is made using the same sample size it will come up with a slightly different value.  The values converge very slowly of the order  .  This property is a consequence of the Central Limit Theorem.

Remark.  Another interesting simulation for approximating    is known as Buffon's Needle problem.  The reader can find many references to it in books, articles and on the internet.  

Mathematica Subroutine (Monte Carlo Pi).

Area Under a Curve

    Monte Carlo simulation can be used to approximate the area   under a curve    for  .  First, we must determine the rectangular box containing as follows.
    
          where  .  
        
Second, randomly pick points    in , where are chosen from independent uniformly distributed random variables over  , respectively.   Third, calculate the ratio as follows:

         , where is number of points that lie in  .  

The area is computed using the approximation,  ,  and we can use the formula  

        .     
    
An "estimate" for the accuracy of the above computation is
    
        .  

Algorithm Monte Carlo Simulation.  Given that     for  .  Use Monte Carlo simulation to approximate the integral  

        .  

Mathematica Subroutine (Monte Carlo Simulation).

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 in the interval and then use the approximation

        .

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