Monte Carlo Methods - Integration.

Integration is the process of determining the area under the curve, the integral of a function is defined as:

For many functions there is an analytical solution, however, some functions do not have analytical solutions and can't be handled with trapezoidal methods and the derivative forms such as Simpson's rule.  A simple two dimensional example with an analytical solution will illustrate the process, take the integral:

The process will vary according to the nature of the function. In this case it is based on the use of two random numbers and a target space.  The target space is a rectangle bounded on the x axis by the minimum and maximum x values and on the y axis by the minimum and maximum values of f(x).

Step 1 - Generate a random number which is between the lower and upper intervals of the integration interval, in this case between 0 and Pi/2 (r1 on the diagram below).

Step 2 - Generate a random number between the minimum and maximum values of the function, in this case between 0 and 1 (r2 on the diagram below).

Step 3 - Using the first random number as the x coordinate and the second random number as the y coordinate, plot the coordinate pair on a graph of the function

This process is illustrated in the diagram below:

If the point falls under the curve accept it, if it falls above it reject it.  Repeat this process a significant number of times, storing the number of accepted values.  At the end of the process determine the value of the integral using the formula:

A program designed to integrate the sample function generated the following results:

The example shows that there is close agreement between the analytical and Monte Carlo methods.  Obviously, the more complex the function and the greater the number of dimensions it occupies, the more complex the program needs to be to perform the integration.

A process similar to Monte Carlo integration forms the basis for the Accept/Reject method of generating random numbers from complex probability density functions.