Monte Carlo Integration

One good use of the Monte Carlo method is called Monte Carlo integration. The goal of integration is to find the area of a shape X; Monte Carlo achieves an estimate of the area by guessing. The method is almost entirely the same as we saw earlier, except that instead of estimating the p of a coin, we are estimating an area. The trick is to reduce this problem to the problem of estimating p of a coin. Our coin flips are performed by randomly choosing points from an area Y that completely encloses X, and whose area we know- if the point is inside X, then we say that it is ``heads'', but if it is outside X, then it is ``tails''. Once we have an estimate on the p for this imaginary coin, we can multiply p by the area of Y to get an estimate of the area of X.

This is described in more detail in algorithm 7.2.

 

 
Figure 7.1:   Code to perform Monte Carlo integration.

It is important to note that if we cannot find a region Y or a function that meets the criteria, then this algorithm cannot be used. Metaphorically, this is because we have no way of determining whether the ``coin'' we just flipped came up heads or tails!

As a concrete example, consider the problem of estimating the area of the quarter circle with a center at zero and a radius of 1. If you recall geometry, you will remember that the area of any circle is , where r is the radius of the circle, Thus, a complete circle with a radius of 1 will have an area of , so our quarter circle will have an area of .

However, if you had forgotten geometry (or simply forgotten what the value of is), then finding the area of this quarter circle would represent a difficult problem to solve without calculus. Let us imagine, for the moment, that this is the case.

By consulting a mathematics textbook and looking at the figure, however, you discover the following pieces of useful information:

1. The quarter circle falls entirely in the square with corners (0,0), (0,1), (1,1), and (1,0).

   This defines Y for our purposes.

2. A circle centered at the origin and radius r is defined as the set of points that satisfy the equation . Therefore, since r in our case is 1, then any point such that is inside the circle, and all other points are outside it.

   Therefore, for our quarter circle, if , then:

   
   
   

   This defines the inside function for our quarter circle.

This leads directly to the implementation of the inside function shown in figure 7.2.

 
Figure 7.2:   The inside function for estimating , using a circle with radius 1, centered at the origin.