# Monte Carlo Integration

## Problem Statement

To estimate $$\mathbb{E}_{p(x)}\left[ f(x) \right]$$.

## Naive Estimator

When $$p(x)$$ are easy to sample from, it is straightforward to estimate $$\mathbb{E}_{p(x)}\left[ f(x) \right]$$ by: $\mathbb{E}_{p(x)}\left[ f(x) \right] \approx \frac{1}{K} \sum_{i=1}^K f(x^{(i)})$ where $$x^{(i)}, \, i = 1 \dots K$$ are i.i.d. samples from $$p(x)$$.

## Importance Sampling

When $$p(x)$$ is not easy to sample from, or when the above estimator has too large variance, one may use the importance sampling estimator: \begin{align} \mathbb{E}_{p(x)}\left[ f(x) \right] = \mathbb{E}_{q(x)}\left[ \frac{f(x)\,p(x)}{q(x)} \right] \approx \frac{1}{K} \sum_{i=1}^K \frac{f(x^{(i)})\,p(x^{(i)})}{q(x^{(i)})} \end{align} where $$x^{(i)}, \, i = 1 \dots K$$ are i.i.d. samples from $$q(x)$$, the proposal distribution. The theoretical optimal proposal distribution $$q^{\star}(x)$$, which gives the smallest variance to the estimator, is given by: $q^{\star}(x) = \frac{\left| f(x) \right|\,p(x)}{\int \left| f(\xi) \right|\,p(\xi)\,d\xi}$

Note the following condition must hold: $q(x) \neq 0, \;\, \forall x \;\, \text{satisfying} \;\, p(x) \neq 0$