Monte Carlo Method

Approximation by repeated random sampling (probabilistic simulation)

Integration technique usually to transform discrete to continuous distribution. For example when we compute the expectation of

f(X)

where

X

has density

p

\mathbb{E}_p[f(X)] = \int f(x)p(x)dx

Assume we have a way of drawing samples from density

p

, we can approximate the integral above by (with access of function

f

and

\hat{f} = \frac{1}{m}\sum_{i=1}^m f(x_i), \quad w_0 \sim p

This is unbiased estimator:

\mathbb{E}\hat{f} = \mathbb{E}[f(X)]

It approximates better as

m

grows.

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)}

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.

\mathbb{V}(\hat{f}) = \mathbb{V}(\frac{1}{m}\sum_{i=1}^mf(X_i)) \\ = \frac{1}{m^2} \mathbb{V}(\sum_{i=1}^mf(X_i))

Since it is

= \frac{1}{m^2} m \mathbb{V}(f(X)) \\ = \frac{1}{m} \mathbb{V}(f(X))

In other words, as

m\rightarrow \infty

, the variance goes to zero.

Monte Carlo Methods