Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to more intuitively understand where the power of Monte Carlo integration comes from for large-dimensional domains of integration.

Other questions on this site have referenced the proof that the scaling of the error in a MC integration goes as $N^{-1/2}$, where $N$ is the number of function evaluations, and does not depend on the dimension $d$ of the domain of integration. On the other hand, the scaling of the error in a uniform sampling integration goes as some power of $N^{-1/d}$. Consequently, for a sufficiently large $d$, one may achieve a desired level of accuracy using a fewer number of function evaluations with a Monte Carlo method than with a uniform numerical quadrature method. The essence of the proof is an invocation of the central limit theorem. I understand the proof on a formal level.

However, I have no intuition for why this proof works. It still seems like "cheating" to me that by either randomly or quasi-randomly selecting the locations to evaluate the function being integrated, you can achieve a more accurate integration than you would by choosing to evaluate the points in a uniform set of spacings (provided that the dimensionality of the integral is large enough).

I have tried to construct an extremely non-rigorous analogy to conducting a statistical survey. One could either poll people at regular distance spacings in a neighborhood, or instead poll the same number of people in completely randomized locations. If there were no correlation between a person's response and the location where that person lives, then I would be able to conclude that my sampling error would be the same using either method. If there were such a correlation after all, then I might bias my results. Is this sort of reasoning at all on the right track to building intuition for the proof?

To phrase my question another way, it seems that when performing a high-dimensional integral you gain accuracy by including a variety of length scales in the points where you evaluate the functions. Why is that? And, is the role of the randomness essentially to ensure that you use a wide range of length scales?

share|improve this question
    
First of all the claim you make sounds false. It is true that in d dimensional space you can estimate the volume under the surface defined by a function f by picking N points unifromly in the space and determining whether or not it is aove or below the value of the function at that point. But it is not true that the accuracy of the estimate for a fixed number N evaluations is independent of the dimension. To the contrary the higher the dimension the less accurate the estimate will be. –  Michael Chernick Jul 6 '12 at 2:36
    
I also do not see how proving or disproving such a claim would have anything to do with the central limit theorem. The reason the method converges to the integral is because the integral represents the fraction of the space that is under the function's surface. Uniform random sampling will cause the percentage of the points under the function's surface to equal the fraction of the volume in the space that is under the functions surface. –  Michael Chernick Jul 6 '12 at 2:44
    
@MichaelChernick You make a good point in your first comment, I made an error in my statement. I meant to say that the scaling of the error with $N$ does not depend on $d$ for the Monte Carlo method (the error goes as $N^{-1/2}$. For a desired level of accuracy, when $d$ becomes sufficiently large, you will be able to use fewer points with the Monte Carlo method than with the uniform sampling method. I will edit my question accordingly. –  kleingordon Jul 6 '12 at 4:40
2  
+1 for the formulation of the question. Somewhat related. –  Did Jul 6 '12 at 6:57
1  
This answer cites a very readable survey article about sparse grids and the course of dimensionality. Regarding your questions, "including a variety of length scales" goes in the right direction, but there are many other intuitive explanations. You could work with space filling curves, investigate enumeration schemes for $\mathbb Z^n$ or look at multivariate polynomials of a fixed degree. What would you prefer for an answer? –  Thomas Klimpel Jul 11 '12 at 5:47

1 Answer 1

up vote 3 down vote accepted
+50

As you correctly point out, the error in a uniform sampling integration goes as some power of $N^{−1/d}$. The problem of uniform sampling is indeed similar to a non-representative statistical survey. Many of the points in a uniform tensor grid don't add much new information. For example, assume that the function you want to integrate looks like $F(x,y)\approx f(x)+g(y)$ in a local square. If you sample this square with a $k\times k$ tensor grid, you will have used $k^2$ evaluations of $F$, but only received information about $f$ and $g$ for $k$ different arguments. A Taylor expansion of $F$ in a local square as $F(x,y)=ax+by+c+O(x^2+y^2)$ indicates that it is indeed not unusual for $F$ to locally look like that. (Note that no term related to $xy$ occurs in this expression.)

To analyze the connection between uniform tensor grids and the Taylor expansion further, let's look at multivariate polynomials of a fixed degree $k$ in $d$ variables. The function values on a $d$-dimensional uniform tensor grid with $k+1$ points in each direction uniquely determine a polynomial where the max degree of each individual variable (in each term) is smaller or equal than $k$. However, the degree (of an individual term) of a polynomial is defined as the sum of the degrees of the individual variables, so that the determined polynomial has degree $dk$ and $(k+1)^d$ individual terms (=degrees of freedom). On the other hand, a general multivariate polynomial of degree $k$ in $d$ variables only has $\frac{(d+k)!}{d!k!}$ individual terms (=degrees of freedom). For fixed $k$, we have $\frac{(d+k)!}{d!k!}=\frac{d^k}{k!} + O(d^{k-1})$, which is polynomial in $d$ (i.e. not exponential).

What has all this to do with randomness and Monte Carlo integration? It might help explain why the naive tensor product approach doesn't break down for Monte Carlo integration, while it does break down for uniform sampling. Unfortunately, there is no straightforward way to turn an effective (naive) randomized algorithm into an effective (naive) deterministic algorithm. However, we know from experience that problems which can be solved efficiently by randomized algorithms normally can also be solved efficiently by (more complicated) deterministic algorithms. The deterministic high-dimensional integration methods I know work by exploiting recursion (divide and conquer) in a clever way. However, this is not the place to explain hierarchical bases, hierarchical subspace splitting or the Smolyak method. A more black-box approach would be to use space-filling curves as a building block instead, where the recursion is already built into the construction of the curve. I don't know how well this would work for integration, but it has been asked here before. At least I know that the research groups investigating applications of sparse grids often also investigate applications of space filling curves.

share|improve this answer
    
Thanks, this was helpful, at least in allowing me to better understand why uniform sampling is sub-optimal. The fact that Monte Carlo methods work so well is still a little bit mysterious to me, but I suppose I will understand more once I look into some of the other deterministic methods you have referenced. –  kleingordon Jul 16 '12 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.