justification of Monte Carlo integration

Question

I came across the following justification of Monte Carlo integration, where $p(x)=\frac{1}{b-a}$

$E[F_N]=E\bigg[ \frac{b-a}{N} \sum \limits_{i=1}^{N}f(X_i) \bigg]$

$= \frac{b-a}{N} \sum \limits_{i=1}^{N} E\big[f(X_i)\big]$

$= \frac{b-a}{N} \sum \limits_{i=1}^{N} \int_a^b f(x)p(x)dx$

$= \frac{1}{N} \sum \limits_{i=1}^{N} \int_a^b f(x)$

$= \int_a^b f(x)$

It looks like you can generalize Monte Carlo integration by choosing $F_N = \frac{1}{N} \sum \limits_{i=1}^{N}\frac{f(X_i)}{p(X_i)} $, since on each small sub-interval, the $p(X_i)$ in the denominator will cancel after applying the expectation. What do you do if you can't find what $p(x)$ is? If you can estimate $p(x)$, how do you tell how close the approximations is?

$E[F_N]=E\bigg[ \frac{1}{N} \sum \limits_{i=1}^{N}\frac{f(X_i)}{p(X_i)} \bigg]$

$= \frac{1}{N} \sum \limits_{i=1}^{N}\frac{f(x)}{p(x)}p(x)dx $

$= \frac{1}{N} \sum \limits_{i=1}^{N}f(x) dx $

$= \int_a^b f(x)dx$

Answer 1

Your justification doesn't really justify Monte Carlo. For one, it says nothing about the convergence of the sum, which is important because if the sum doesn't converge fast enough there's no point in Monte Carlo.

Intuitive justification is built differently. You start with an estimator of a sample mean, so you draw a sample $x_1,x_2,\dots,x_N$ from a distribution with density $f$ then estimate the mean of the function:

$$\bar g=\frac{1}{N}\sum_{i=1}^N g(x_i)$$

Then you invoke the central limit theorem, to see that $$\bar g\sqrt N \approx\mathcal{N}(\mu_g,\sigma_g^2)$$ where $$\sigma_{\bar g}=\frac{\sigma_g}{\sqrt N}$$

Now, you see that the convergence rate is $\sqrt N$, i.e. you start with the variance of $g$ (constant) then shrink it with every new loop of your Monte Carlo until it's small enough. This may or may not be OK for you.

Next, look at the value to which it converges: $$\mu_g=\int_a^b f(x) g(x) dx$$ by definition of the mean, where $f(x)$ is the probability density function (pdf) of your distribution.

For instance, when $f$ corresponds to the uniform distribution over $(a,b)$, you get $$=\frac{1}{b-a}\int_a^b g(x)dx$$ Voilà, you see the integral that you were trying to approximate, $\int_a^b g(x)dx$.

Now, you see that the integral can be approximated using Monte Carlo because:

• it converges to the value you were looking for
• and you know that it converges at $\sqrt N$ speed

That's the justification. Obviously, I'm being liberal with notation and rigor, but that's not what you're after anyways.

I can recommend the simplest intro to Monte Carlo by none other than Sobol (known to most by Sobol sequences). This book is a translation of a little book written for high school students in USSR. It starts with an easy and intuitive explanation of the method with application to integration on p.59. It has the case for non-uniform distributions, which is also explained very simply.