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 \]