2010-07-16

A personal annotations of Veach's thesis (9)

Page 50: Stratified

I was not familiar with the word `Stratified.' A Monte-Carlo method usually uses a pseudo random number sequence. A random number sequence usually should have a property, `unexpectedness,' this means a same number sequence like 1, 1, 1, 1, 1, ..., 1 could be also a part of random number sequence. This issue is well explained in Knuth's book (D.E.Knuth, The Art of Computer Programming, Vol.2 Random numbers). The sampling pattern could be the left of Figure 1.

 Figure 1. Stratified example. Left example of random 12 samples (clumping problem), Right example of 2x2 stratified random 12 samples

In Figure 1 left, some part is not well sampled, or some part is oversampled -- the sampling pattern is biased. This is clumping, a bad luck in a sense. Usually it is solved when the number of samples is increased, but, it computationally costs, means it takes more time to compute. To solve this clumping problem without losing performance, the sampling region is subdivided --- or stratified. In this way, even we have a bad luck, still we could sample more uniformly. This method is called a stratified method. Readers might wonder, ``then why don't you sample uniformly?'' Uniform sampling can avoid clumping problem, but, the uniform sampling causes another problem, ``Aliasing problem'' by the sampling theorem. My friend said that ``the Quasi-Monte-Carlo method is a good stratified method.''



Acknowledgements

Special thanks to Daniel S. and Leonhard G. who explained me what is the Stratified method.

No comments: