6. Independent Monte Carlo

Suppose we want to compute for some function $h: \mathbb{R}^k\rightarrow\mathbb{R}$,

$$ \mathbb{E}_f[h(X)] = \int h(x)f(x)\,dx. $$

If we could simulate $x_1,\dots,x_n\stackrel{\text{i.i.d.}}{\sim} f$, then by the law of large numbers, we would have

$$ \frac{1}{n}\sum_{i=1}^n h(x_i) \longrightarrow \mathbb{E}_f[h(X)]. $$

Furthermore, we have that

$$ \text{Var}\left(\frac{1}{n}\sum_{i=1}^n h(x_i)\right) = \frac{1}{n^2}\sum_{i=1}^n \text{Var}(h(X_i)) = \frac{1}{n}\text{Var}(h(X_1)), $$

which, we will note for now, does not depend on the dimension of the random variable $X_1$.

This approach to computing the expectation above is known as Monte Carlo integration which takes advantage of the law of large numbers saying that averages of numbers converge to their expectation. Monte Carlo integration can be quite useful, but it takes the problem of computing the integral directly (or via approximation) and replaces it with a problem of drawing samples from an arbitrary density function $f$.

Before we go further, we will take a brief diversion into random number generation.