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    is continuous over  ,  then there exists a number  ,  with  ,  such that  

        .

This can be written in the equivalent form:

        .  

Remark.  This computation shows that the area under the curve is the base width    times the "average height"  .

Composite Midpoint Rule

    An intuitive method of finding the area under a curve    is to approximate that area with a series of rectangles that lie above the intervals  .  

Theorem (Composite Midpoint Rule).  Consider    over .  Let the interval   be subdivided into    subintervals    of equal width  .  Form the equally spaced nodes    for  .  The composite midpoint rule for  n  subintervals is  

        .  

This can be written in the equivalent form  

        ,     where     .   

Corollary (Remainder term for the Midpoint Rule)  The composite midpoint rule    is an numerical approximation to the integral, and  

        .   

Furthermore, if ,  then there exists a value    with    so that the error term    has the form  

        .  

This is expressed using the "big " notation  .  

Algorithm Composite Midpoint Rule.  To approximate the integral  

        ,  

by sampling    at the    equally spaced points    for  ,  where  .  

Mathematica Subroutine (Midpoint Rule).

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   in the interval  .    

(ii)    Determine the average value of the function  

         .  

(iii)    Compute the approximation to the integral  

        .

(iv)    An estimate for the error is

        ,     where     .  

    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    will produce more accurate approximations.  The values converge very slowly of the order  .  This property is a consequence of the Central Limit Theorem.

Mathematica Subroutine (Monte Carlo for 1 Dimensional Integrals).

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

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   .  We can apply the inequality  

          when    

to see that  Monte-Carlo integration will usually converge faster for quintuple multiple integrals and higher, i.e. , 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    in the "volume"   .    

(ii)    Determine the average value of the function  

         .  

(iii)    Compute the approximation to the integral  

        .

(iv)    An estimate for the error is

        ,     where     .  

Mathematica Subroutine (Monte Carlo for 3 Dimensional Integrals).