Module

for

Monte Carlo Integration

 

Background

    We will be discussing how to approximate the value of an integral based on the average of function values.  The following concept is useful.

Theorem  (Mean Value Theorem for Integrals).  If  [Graphics:Images/MonteCarloMod_gr_1.gif]  is continuous over  [Graphics:Images/MonteCarloMod_gr_2.gif],  then there exists a number  [Graphics:Images/MonteCarloMod_gr_3.gif],  with  [Graphics:Images/MonteCarloMod_gr_4.gif],  such that  

        [Graphics:Images/MonteCarloMod_gr_5.gif].

This can be written in the equivalent form:

        [Graphics:Images/MonteCarloMod_gr_6.gif].  

Remark.  This computation shows that the area under the curve is the base width  [Graphics:Images/MonteCarloMod_gr_7.gif]  times the "average height"  [Graphics:Images/MonteCarloMod_gr_8.gif].  

 

Example 1.  Let  [Graphics:Images/MonteCarloMod_gr_9.gif].  Find  [Graphics:Images/MonteCarloMod_gr_10.gif]  so that  

        [Graphics:Images/MonteCarloMod_gr_11.gif].

Solution 1.

 

Composite Midpoint Rule

    An intuitive method of finding the area under a curve  [Graphics:Images/MonteCarloMod_gr_17.gif]  is to approximate that area with a series of rectangles that lie above the intervals  [Graphics:Images/MonteCarloMod_gr_18.gif].  

Theorem (Composite Midpoint Rule).  Consider  [Graphics:Images/MonteCarloMod_gr_19.gif]  over [Graphics:Images/MonteCarloMod_gr_20.gif].  Let the interval  [Graphics:Images/MonteCarloMod_gr_21.gif] be subdivided into  [Graphics:Images/MonteCarloMod_gr_22.gif]  subintervals  [Graphics:Images/MonteCarloMod_gr_23.gif]  of equal width  [Graphics:Images/MonteCarloMod_gr_24.gif].  Form the equally spaced nodes  [Graphics:Images/MonteCarloMod_gr_25.gif]  for  [Graphics:Images/MonteCarloMod_gr_26.gif].  The composite midpoint rule for  n  subintervals is  

        
[Graphics:Images/MonteCarloMod_gr_27.gif].  

This can be written in the equivalent form  

        
[Graphics:Images/MonteCarloMod_gr_28.gif],     where     [Graphics:Images/MonteCarloMod_gr_29.gif].  

Module  Midpoint Rule  

Corollary (Remainder term for the Midpoint Rule)  The composite midpoint rule  [Graphics:Images/MonteCarloMod_gr_30.gif]  is an numerical approximation to the integral, and  

        
[Graphics:Images/MonteCarloMod_gr_31.gif].   

Furthermore, if [Graphics:Images/MonteCarloMod_gr_32.gif],  then there exists a value  [Graphics:Images/MonteCarloMod_gr_33.gif]  with  [Graphics:Images/MonteCarloMod_gr_34.gif]  so that the error term  [Graphics:Images/MonteCarloMod_gr_35.gif]  has the form  

        [Graphics:Images/MonteCarloMod_gr_36.gif].  

This is expressed using the "big [Graphics:Images/MonteCarloMod_gr_37.gif]" notation  [Graphics:Images/MonteCarloMod_gr_38.gif].  

Module  Midpoint Rule  

Animations  Midpoint Rule  

 

Algorithm Composite Midpoint Rule.  To approximate the integral  

        [Graphics:Images/MonteCarloMod_gr_39.gif],  

by sampling  [Graphics:Images/MonteCarloMod_gr_40.gif]  at the  [Graphics:Images/MonteCarloMod_gr_41.gif]  equally spaced points  [Graphics:Images/MonteCarloMod_gr_42.gif]  for  [Graphics:Images/MonteCarloMod_gr_43.gif],  where  [Graphics:Images/MonteCarloMod_gr_44.gif].  

 

Computer Programs  Midpoint Rule  

Mathematica Subroutine (Midpoint Rule).

[Graphics:Images/MonteCarloMod_gr_45.gif]

Example 2.  Let  [Graphics:Images/MonteCarloMod_gr_46.gif].  Use the midpoint rule to calculate approximations to the integral  [Graphics:Images/MonteCarloMod_gr_47.gif].
Solution 2.

 

Monte Carlo Method

    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.  

 

Approximation for an Integral

    The Monte Carlo method can be used to numerically approximate the value of an integral.  For a function of one variable the steps are:  

(i)    Pick n randomly distributed points  [Graphics:Images/MonteCarloMod_gr_67.gif] in the interval  [Graphics:Images/MonteCarloMod_gr_68.gif].    

(ii)    Determine the average value of the function  

         [Graphics:Images/MonteCarloMod_gr_69.gif].  

(iii)    Compute the approximation to the integral  

        [Graphics:Images/MonteCarloMod_gr_70.gif].

(iv)    An estimate for the error is

        [Graphics:Images/MonteCarloMod_gr_71.gif],     where     [Graphics:Images/MonteCarloMod_gr_72.gif].  

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

Proof  Monte Carlo Integration  

 

Computer Programs  Monte Carlo Integration  

Mathematica Subroutine (Monte Carlo for 1 Dimensional Integrals).

[Graphics:Images/MonteCarloMod_gr_75.gif]

The above subroutine is all we need to "do the math."  The following subroutine presents the results in a nice format.

[Graphics:Images/MonteCarloMod_gr_76.gif]

Example 3.  Let  [Graphics:Images/MonteCarloMod_gr_77.gif].  Use the Monte Carlo method to calculate approximations to the integral  [Graphics:Images/MonteCarloMod_gr_78.gif].
Solution 3.

 

Example 4.  Let  [Graphics:Images/MonteCarloMod_gr_101.gif].  Use the Monte Carlo method to calculate approximations to the integral  [Graphics:Images/MonteCarloMod_gr_102.gif].
Solution 4.

 

Example 5.  Let  [Graphics:Images/MonteCarloMod_gr_125.gif].  Use the Monte Carlo method to calculate approximations to the integral  [Graphics:Images/MonteCarloMod_gr_126.gif].
Solution 5.

 

Approximation for a Double Integral

    The Monte Carlo method can be used to numerically approximate the value of a double integral.  For a function of two variables the steps are:  

(i)    Pick n randomly distributed points  [Graphics:Images/MonteCarloMod_gr_149.gif] in the rectangle  [Graphics:Images/MonteCarloMod_gr_150.gif].    

(ii)    Determine the average value of the function  

         [Graphics:Images/MonteCarloMod_gr_151.gif].  

(iii)    Compute the approximation to the integral  

        [Graphics:Images/MonteCarloMod_gr_152.gif].

(iv)    An estimate for the error is

        [Graphics:Images/MonteCarloMod_gr_153.gif],     where     [Graphics:Images/MonteCarloMod_gr_154.gif].  

 

Mathematica Subroutine (Monte Carlo for 2 Dimensional Integrals).

[Graphics:Images/MonteCarloMod_gr_155.gif]

The above subroutine is all we need to "do the math."  The following subroutine presents the results in a nice format.

[Graphics:Images/MonteCarloMod_gr_156.gif]

Example 6.  Let  [Graphics:Images/MonteCarloMod_gr_157.gif].  Use the Monte Carlo method to calculate approximations to the double integral  

        [Graphics:Images/MonteCarloMod_gr_158.gif].  

Solution 6.

 

Example 7.  Let  [Graphics:Images/MonteCarloMod_gr_178.gif].  Use the Monte Carlo method to calculate approximations to the double integral  

        [Graphics:Images/MonteCarloMod_gr_179.gif].  

Solution 7.

 

Iterated Integrals in Higher Dimensions

    Sometimes we are given integrals which cannot be done analytically, especially in higher dimensions where the standard  methods of discretization can become computationally expensive.  For example, the error in the composite midpoint rule (and the composite trapezoidal rule) of an d-dimensional integral has the order of convergence   [Graphics:Images/MonteCarloMod_gr_199.gif].  We can apply the inequality  

        [Graphics:Images/MonteCarloMod_gr_200.gif]  when  [Graphics:Images/MonteCarloMod_gr_201.gif]  

to see that  Monte-Carlo integration will usually converge faster for quintuple multiple integrals and higher, i.e. [Graphics:Images/MonteCarloMod_gr_202.gif], etc.  

 

Approximation for a Multiple Integral

    The Monte Carlo method can be used to numerically approximate the value of a multiple integrals.  For a function of d variables the steps are:  

(i)    Pick n randomly distributed points  [Graphics:Images/MonteCarloMod_gr_203.gif]  in the "volume"   [Graphics:Images/MonteCarloMod_gr_204.gif].    

(ii)    Determine the average value of the function  

         [Graphics:Images/MonteCarloMod_gr_205.gif].  

(iii)    Compute the approximation to the integral  

        [Graphics:Images/MonteCarloMod_gr_206.gif].

(iv)    An estimate for the error is

        [Graphics:Images/MonteCarloMod_gr_207.gif],     where     [Graphics:Images/MonteCarloMod_gr_208.gif].  

 

Mathematica Subroutine (Monte Carlo for 3 Dimensional Integrals).

[Graphics:Images/MonteCarloMod_gr_209.gif]

Example 8.  Let  [Graphics:Images/MonteCarloMod_gr_210.gif].  Use the Monte Carlo method to calculate approximations to the triple integral  

        [Graphics:Images/MonteCarloMod_gr_211.gif].  

Solution 8.

 

Mathematica Subroutine (Monte Carlo for 4 Dimensional Integrals).

[Graphics:Images/MonteCarloMod_gr_221.gif]

Example 9.  Let  [Graphics:Images/MonteCarloMod_gr_222.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_223.gif].  

Solution 9.

 

Mathematica Subroutine (Monte Carlo for 5 Dimensional Integrals).

[Graphics:Images/MonteCarloMod_gr_232.gif]

Example 10.  Let  [Graphics:Images/MonteCarloMod_gr_233.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_234.gif].  

Solution 10.

 

Example 11.  Let  [Graphics:Images/MonteCarloMod_gr_246.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_247.gif].  

Solution 11.

 

Example 12.  Let  [Graphics:Images/MonteCarloMod_gr_264.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_265.gif].  

Solution 12.

 

Example 13.  Let  [Graphics:Images/MonteCarloMod_gr_274.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_275.gif].  

Solution 13.

 

Example 14.  Let  [Graphics:Images/MonteCarloMod_gr_284.gif].  Use the Monte Carlo method to calculate approximations to the integral  

        [Graphics:Images/MonteCarloMod_gr_285.gif].  
        
Compare the Monte Carlo method with the midpoint rule.

Solution 14.

 

Research Experience for Undergraduates

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

 

Download this Mathematica Notebook Monte Carlo Integration

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2005