### What's the Area? (Part V)

This is Part 5 of a series discussing methods of integration (here are links to 1, 2, 3 and 4). The last post looked at a case of Monte Carlo Integration, which amounted to a shotgun approach in which the proportion of random points falling inside the boundaries of a trapezoid was used to estimate its area.

Although it's called

Although sequential, uniform sampling is standard and works well in areas such as digital signal processing, it doesn't typically work well with Monte Carlo Integration (for reasons that may be obvious).

Given my calling the previous case

I ran a test sampling uniformly from left to right and top to bottom. Due to the fact the trapezoid occupies mostly the bottom half of the unit cube, things don't get close to the magic 0.55 until we've sampled the most of the space... (please excuse Blogger's lack of support for decent indentation)...

iterations estimate relative error

---------- -------- --------------

10^1 1.000000 0.818182

10^2 1.000000 0.818182

10^3 1.000000 0.818182

10^4 1.000000 0.818182

10^5 1.000000 0.818182

10^6 0.550398 0.000724

In comparison, here are the results we obtained through random sampling...

iterations estimate relative error

---------- -------- --------------

10^1 0.500000 0.090909

10^2 0.530000 0.036364

10^3 0.510000 0.072727

10^4 0.540500 0.017273

10^5 0.549610 0.000709

10^6 0.550114 0.000207

Uniform sampling didn't work well. Random sampling worked better. Are there even better means of sampling the space? This question brings us to the point where I think the problem becomes much more interesting.

In Part 6, we'll find an answer.

Although it's called

*Monte Carlo*, this numerical integration strategy doesn't require points to be selected randomly. Other sampling methods can be employed with varying results.Although sequential, uniform sampling is standard and works well in areas such as digital signal processing, it doesn't typically work well with Monte Carlo Integration (for reasons that may be obvious).

Given my calling the previous case

*the shotgun approach*, the case of uniform sampling strategy might be called*the peg board*approach...I ran a test sampling uniformly from left to right and top to bottom. Due to the fact the trapezoid occupies mostly the bottom half of the unit cube, things don't get close to the magic 0.55 until we've sampled the most of the space... (please excuse Blogger's lack of support for decent indentation)...

iterations estimate relative error

---------- -------- --------------

10^1 1.000000 0.818182

10^2 1.000000 0.818182

10^3 1.000000 0.818182

10^4 1.000000 0.818182

10^5 1.000000 0.818182

10^6 0.550398 0.000724

*(Note: this is a case where a logarithmic scale for sample count really doesn't tell the story very well. A linear scale of 100,000 per step would demonstrate things better with gradual linear improvements from 100,000 to 1,000,000.)*In comparison, here are the results we obtained through random sampling...

iterations estimate relative error

---------- -------- --------------

10^1 0.500000 0.090909

10^2 0.530000 0.036364

10^3 0.510000 0.072727

10^4 0.540500 0.017273

10^5 0.549610 0.000709

10^6 0.550114 0.000207

Uniform sampling didn't work well. Random sampling worked better. Are there even better means of sampling the space? This question brings us to the point where I think the problem becomes much more interesting.

In Part 6, we'll find an answer.

## 0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home