Monte Carlo integration is another technique for estimating an integral numerically. There is a short section in our text on the topic (Chapter 13). The method takes a bound on the region of integration, then randomly selects points within this bound (from a uniform distribution). For each random point, it checks to see if the point is actually in the region of integration, then if so does a function evaluation, then averages all the function evaluations together. Using the volume of the bound for the region and the fraction of the random points that are in the region, we can approximate the volume of the region. Then, we can estimate the integral as the volume of the region times the average value of the function evaluations. By the law of large numbers, the expected magnitude of our error deceases by a factor of 1/sqrt(n) as we increase n, or quadrupling the number of points will half our error.

While this is not any better than other techniques we have learned in class for one dimensional integrals, it becomes much better than other methods for integrals with high dimensions. This is because the other methods we have discussed must create a grid of function evaluations separated by h in the domain, (where as we decrease h we decrease our error). Thus the number of points needed grows exponentially as we increase the number of dimensions. For this method however, the number of dimensions does not matter (while the variance of our estimate is related to the volume, if we fix the volume while increasing the number of dimensions, it does not effect the variance our estimate).

More complicated techniques can further improve this method. One enhancement is to change the distribution used to select points for function evaluation while the algorithm is running to increase the density near areas where the function behaves wildly.

In addition to our text, here are a couple of other things to look at:
http://en.wikipedia.org/wiki/Monte_Carlo_Integration
http://en.wikipedia.org/wiki/Monte_Carlo_method

The title of this article was significantly better than its content:
http://en.wikipedia.org/wiki/Curse_of_dimensionality

Here is a power point presentation on applications of Monte Carlo Integration in graphics:
graphics.cs.ucdavis.edu/~bcbudge/ecs298_2004/montecarlo.ppt