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 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.
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.
posted by metamerist at
8:55 PM
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home