Integral

Integral Notion

Assume you have a difficult integral to compute

\int f(x)dx = \int \frac{f(x)}{g(x)} g(x) dx = \mathbb{E}_g [\frac{f(X)}{g(X)}] \approx \frac{1}{m}\sum_{i=1}^m \frac{f(X_i)}{g(X_i)}, X_i \sim g

\mathbb{E}_g[w(X)] \approx \frac{1}{m}\sum_{i=1}^m w(X_i), w(X) = \frac{f(X)}{g(X)}

The Monte Carlo estimator for

E[f(X)]

performs better than sampling from the original distribution when it has lower variance. For comparison, the variance of

I=\frac{1}{N}\sum f(x_i)

\frac{1}{N}V(X)

, while the variance of

\frac{1}{N}\sum_g{f(x_i)\frac{p(x_i)}{g(x_i)}}

\frac{1}{N}V(f(x)\frac{p(x)}{g(x)})

- with lower variance being preferable.

p(y) = \int p(x,y)dx = \int g(x) \frac{p(x,y)}{g(x)}dx = \mathbb{E}_g[w(X)]

\mathbb{E}_{p(X|Y)}[f(X)] = \int p(x|Y)f(x)dx \\= \int \frac{p(x, Y)}{p(Y)} f(x)dx \\= \frac{1}{p(Y)} \int p(x, Y)f(x)dx\\ = \frac{1}{p(Y)} \int \frac{g(x)}{g(x)} p(x, Y)f(x)dx \\= \frac{\mathbb{E}_{g}[w(X)f(X)]}{\mathbb{E}_{g}[w(X)]} \approx \frac{\frac{1}{m}\sum_{i=1}^m w(X_i)f(X_i)}{\frac{1}{m}\sum_{i=1}^m w(X_i)}

W_i = \frac{w(X_i)}{\sum_{j=1}^mw(X_j)}, E_{p(X|Y)}(f(X)) \approx \sum_{i=1}^m W_if(X_i)

p(x|y) = \sum_{i=1}^m W_i \delta_{x_i}(x)

In short, Monte Carlo methods enable us to estimate any integral by random sampling. In

Evidence is also form of integral so it becomes tractable.