Monte-Carlo Integration

Motivation

How do we evaluate high-dimensional integrals numerically? For example, consider $N$ particles ${\underline{x}}_1,{\underline{x}}_2,\dots ,{\underline{x}}_N\in {\mathbb{R}}^3$. The Joint PDF is $f:{\mathbb{R}}^{3N}\to [0,\infty )$. If we wanted to find the average of some property $g$ among all particles, we’d have to do

$${\int }_{{\mathbb{R}}^{3N}}g(x)f(x)d\underline{x}$$

which is obviously expensive.

Algorithm (Monte Carlo Integration)

The goal is to evaluate

$$I={\int }_{D}g(x)f(x)dx$$

where $D\subseteq {\mathbb{R}}^{\ell }$ is bounded, $f$ is a PDF on $D$, and $g$ is integrable.

1. Generate $X_1,\dots ,X_N\sim f$ which are iid.
2. Set $$I_N=\frac{1}{N}\sum _{i=1}^{N}g(X_i)\approx I$$ where $I_N$ is a MC estimator of $I$ or a crude MC (CMC Estimator) of $I$.

We want to know,

1. Does $I_N$ converge? As $N\to \infty ,I_N\to I$?
2. What is the error? As $N\to \infty$ what is $|I_N-I|$? The idea is to look at $\mathbb{E}\left\{I_N\right\}$ and $\text{Var}(I_N)$.

How “good” is $I_N$ for some $N$?

Proposition (MC Estimators Mean & Variance)

Claim:

$$\begin{array}{rl}\mathbb{E}\left\{I_N\right\}& =I\\ \text{Var}(I_N)& =\frac{1}{N}\text{Var}(g(X))=\frac{1}{N}\left[{\int }_{D}g(x{)}^{2}f(x)dx-I^2\right]\end{array}$$

or that

1. $I_N$ is unbiased
2. $X\sim f$

Proof:

First,

$$\begin{array}{rl}\mathbb{E}\left\{I_N\right\}& =\frac{1}{N}\sum _{n=1}^N\mathbb{E}\left\{g(X)\right\}\\ & =\frac{1}{N}\cdot NI=I\end{array}$$

by linearity of $\mathbb{E}$. Second,

$$\begin{array}{rlr}\text{Var}(I_N)& =\text{Var}\left(\frac{1}{N}\sum _{n=1}^{N}g(X_n)\right)& \\ & =\frac{1}{N^2}\text{Var}\left(\sum _{n=1}^{N}g(X_n)\right)& \\ & =\frac{1}{N^2}\sum _{n=1}^N\text{Var}(g(X_n))& \text{by independence}\\ & =\frac{1}{N^2}\cdot N\text{Var}(g(X))& \text{by identically distributed}\\ & =\frac{1}{N}\text{Var}(g(X))& \end{array}$$

as required. See Variance Reduction on how we can reduce the variance of the MC Estimator.

Theorem (Strong Consistency of MC Estimators)

$$\underset{N\to \infty }{\lim }{I}_N=I$$

with probability $1$.

Proof: This follows from the Strong Law of Large Numbers.

This theorem tells us that if we run the simulation “long enough” we are guaranteed to get the correct answer. In particular, $P\left({\lim }_{N\to \infty }{I}_N=I\right)=1$.

Theorem (Asymptotic Normality of MC Estimators)

Let ${\sigma }^2=\text{Var}(g(X))$ where $X\sim f$. Then

$$\frac{I_N-I}{\sigma /\sqrt{N}}\to Z\sim N(0,1)$$

Proof: By Central Limit Theorem.

This theorem tells us that we can calculate exactly how much error/noise is in our estimate and build confidence intervals.