Choice of Monte Carlo Sampling Distribution

I have made several posts on the basics of Monte Carlo integration techniques. I introduced the topic using MC integration to estimate the value of π. Then I took a look at the way the convergence characteristics of the estimate depend upon the number of trials. Finally, I looked at how the relative size of the area being estimated affects convergence. Finally, I want to put some of these pieces together and introduce a final basic concept: the choice of Monte Carlo sampling distribution.

For this post I will return to the example of estimating π from a quarter-circle inside a square, only this time I am going to change the shape of the search space from a square to a triangle. I want to do this because, as you can see from the chart at the right, all the “information” about π is contained in the top right half of the square containing the quarter circle. A randomly selected point can fall anywhere in the bottom left corner and it tells us nothing about the shape of the curve – so why put any points there at all?

To take advantage of my observation about where the information is located in the x-y plane, I need to be a bit cleverer about my distribution: I want the probability of randomly selecting a point in the bottom left corner to be zero, and the probability of selecting any point in the top right to be constant.

I am doing this with one of two objectives in mind:

1. The area of the upper right triangle is half that of the square. So for any given number of trials, the density of points will be double if I use the triangle rather than the square. As my second post on MC, this buys me a reduction in the error of my estimate of 1/√2. Alternatively, I need only run 1/√2 as many trials to get the same accuracy as when I use the whole square.
2. If the area of interest occupies a greater proportion of the sample space, then as discussed in my third MC post, my accuracy will increase further still (or I can use fewer trials). The area under the curve occupies 57% of the triangle ((pi/4 – 1/2) / 1/2 = 57%) vs 79% of the square (pi/4 / 1 = 79%). So, in this case, I will give up a little of my gains from the effect discussed in 1 above, to this effect.

I start by considering the probability distribution I want to sample from to get my x values. I want to randomly pick any place in the triangle with equal probability. Let’s say that A(x) is the total area integrating over x from 0 to x. Obviously A(x) = x^2 / 2 (area of a triangle = 1/2 x base x perp height). I want to randomly sample, uniformly, from 0 to A, the total area. So we can say A(x) ~U(0, A), and therefore:

y is then uniformly sampled between x and 1: y ~ U(x, 1)

Was it worth it? Using the square I estimated a value for π/4. Using the triangle I estimated a value for π/2. Let’s say we want the same % error using both approaches, and I want to calculate the number of trials necessary using the triangle method to give me the same accuracy as 10,000 trials using the square. So I solve the following using the form %error = √(p.(1 – p) / trials) / p:

The charts below show 1,000 simulations of 10,000 trials using the square distribution on the left and the triangle distribution with 3634 trials on the right. The blue points model a normal distribution. As you can see, their respective % errors are in the same ballpark!

If I haven’t bored you to death with this yet, I have one more post I want to do on MC, which I hope will show a really interesting progression of these ideas: stratification.