There are many problems for which Monte Carlo integration is the most efficient method available.

(Emphasis mine.) I know I’m late to the party, but I just noticed this. While what you say it’s true, “available” in this case means “that we know of”, not “that is possible”. I’m not an expert, but IIRC the point of the MCI is that the functions are hard to analyze. You could integrate analogously without randomization (e.g., sample the integration domain on a regular grid), and it very well might work. The problem is that if the function you integrate happens to behave atypically on the regular grid with respect to its global behavior (e.g., if the function has some regular features with a frequency that accidentally matches that of your grid, you might sample only local maxima, and severely overestimate the integral).

But for an individual function there certainly exists (for some values of “certainly”) an ideal sampling that yields an excellent integration, or some even better method that doesn’t need sampling. But, you need to understand the function very well, and search for that perfect evaluation strategy, and do this for every individual function you want to integrate. (Not a math expert here, but I suspect in the general case that grid would be impossible to find, even if it exists, and it’s probably very hard even for those where the solution can be found.)

So what MCI does is exactly what Eliezer mentions above: you randomize the sampling as well as you can, to avoid as much as possible tripping an unexpected “resonance” between the grid and the function’s behavior. In effect, you’re working against an environment you can’t overwhelm by being smart, so you brute force it and do your best to reduce the ways the environment can overwhelm you, i.e. you try to minimize the worst-case consequences.

Note that for functions we really understand, MCI is not by far the best method. If you want to integrate a polynomial, you just compute the antiderivative, evaluate it in two points, subtract, and you’re done. MCI is nice because in general we don’t know how to find out the antiderivative. In analogy with tic-tac-toe, integration would be the game, and each function is a different opponent; a polynomial is an adversary we can anticipate as well as Omega can model a human—in fact, we don’t even need to evaluate the function, we can deduce directly what the result of “its actions” will be; but most functions (probably almost all) are so difficult adversaries that we can’t do better than try to limit how badly they can screw us.

(I have a vague recollection of an anecdote about MCI: Someone somewhere was using it to do a complicated multiple integral, and got very silly results. Turns out, while the pseudo-random generator looked OK by itself, when its output was distributed throughout the complicated multi-dimensional space that was sampled, a non-obvious regularity in the generated numbers happened to match something the function did. So, in effect, the function beat them. In other words (ignoring that this is apocryphal), you don’t even need a very smart opponent to be screwed, a hard function is enough... That quantum noise generator can be very handy.)