COMP0187 Lecture 9

Sampling

Monte Carlo Method

Elementary

Elementary Monte Carlo identity

Trick

The stochasticity trick of Monte Carlo method (
Importance sampling)

Assume you have a difficult integral to compute

The Monte Carlo estimator for performs better than sampling from the original distribution when it has lower variance. For comparison, the variance of is , while the variance of is - with lower variance being preferable.

Importance sampling

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

Bayesian Statistics,

Evidence is also form of integral so it becomes tractable.

MCMC

importance sampling degrades possibly exponentially badly as the dimension of the latent variables increase, unless we have an insanely good proposal since the

Curse of dimensionality and usually cover large volumes.

Time-homogeneous Markov