In class today we began discussing methods of numerical integration.  Doing research upon methods of approximating definite integrals, I came across the Monte Carlo integration, and Monte Carlo methods in general. 

Monte Carlo methods utilize random numbers to randomly sample from the domain in order to (accurately) compute the desired result.  In Monte Carlo integration, for example, we randomly select points at which we evaluate the integral.  This contrasts traditional methods of numerical integration, in which we sample the points at regular intervals.  The estimations of the Monte Carlo integral can be improved by using heuristics to determine areas in the domain where we should sample more points from. 

Monte Carlo integration is especially useful in approximating integrals in higher dimensions.  According to Wikipedia, “To numerically integrate a function of a two-dimensional vector, equally spaced grid points over a two-dimensional surface are required.  For instance a 10×10 grid requires 100 points.  If the vector has 100 dimensions, the same spacing on the grid would require 10^100 points.”  In such an instance, it is clear that sampling from evenly spaced intervals is inefficient. 

Another popular use of the Monte Carlo method  is to estimate the value of pi.  To do this, we draw a square of length 1 and inscribe a circle inside.  Then, by randomly sampling points in the square, we know that by basic probability, pi/4 of the points are expected to lie in the circle.  For example, suppose that we sample 1000 points in the square, and in our sampling we find that 790 of the points lie in the square.  Then we know that 790/1000 is approximately pi/4, so that pi is approximately 4*.79=3.16 .

Note that in order for Monte Carlo methods to be applicable, we must have a good way of generating random or pseudorandom numbers.  If in our pi example the points we selected were not really random, e.g there is a higher probability of picking a point in the center of the square than closer to a corner of the square, then our approximation will not be accurate at all.  Furthermore, it is important to note that the accuracy of the Monte Carlo method increases as we take more samples, because as we increase the number of sampling points, the result will converge to the expected value.   These two properties remain true for all Monte Carlo methods, in general.

References: 

1.  http://en.wikipedia.org/wiki/Monte_Carlo_integration

2.  http://kids.dzone.com/news/monte-carlo-pi-and-gambling