Monte Carlo Integration
| Item | Description |
|---|
I = Integral f(x) dx = Integral [f(x)/g(x)] * g(x) dx | Rewrite integral as expectation under proposal distribution g |
MC Estimate: I_hat = (1/n)*Sum(f(x_i)/g(x_i)) | Sample x_i from g, compute average — unbiased estimator |
Convergence: O(1/sqrt(n)) | Independent of dimension! — the key advantage of MC |
Confidence Interval: +/- z_alpha*sigma/sqrt(n) | Standard error shrinks with sqrt(n) |
Crude MC: g = uniform | Simplest — sample uniformly, but high variance in high dimensions |
Variance Reduction Goal | Reduce sigma without increasing n — importance sampling, control variates |
Importance Sampling
| Item | Description |
|---|
I = E_f[h(x)] = E_g[h(x)*f(x)/g(x)] | Sample from proposal g, weight by importance ratio f/g |
Optimal g ∝ |h(x)|*f(x) | Oracle proposal — zero variance in theory, impractical |
Effective Sample Size (ESS) | n * (E[w])^2 / E[w^2] — measures how many samples are actually useful |
Degeneracy | Few samples dominate weights — widespread in high dimensions; use resampling |
Sequential Importance Sampling (SIS) | Particle filters — importance sampling in sequential setting |
Pitfalls | Importance ratio can have infinite variance if g has thinner tails than f |
MCMC Techniques
| Item | Description |
|---|
Metropolis-Hastings | Propose new state; accept with probability min(1, ratio of posteriors) |
Proposal Distribution | Gaussian centered at current state — too narrow=slow, too wide=low acceptance |
Optimal Acceptance Rate | ~23.4% for random-walk MH in high dimensions — target this |
Gibbs Sampling | Sample each parameter from its full conditional — works well for conjugate models |
Burn-in Period | Discard initial samples before chain reaches stationary distribution |
Thinning | Keep every k-th sample — reduces autocorrelation but wastes computation |
Applications
| Item | Description |
|---|
Bayesian Inference | Draw samples from posterior when analytic form unavailable |
Bootstrap | Resampling technique for uncertainty quantification — see confidence intervals sheet |
Permutation Tests | Shuffle labels to generate null distribution — non-parametric testing |
Option Pricing in Finance | MC simulation of stochastic processes for complex derivatives |
A/B Testing via Simulation | Simulate results under different effect sizes to estimate power |
Pro Tip: The core Monte Carlo idea: use randomness to solve deterministic problems. The estimate converges at rate 1/sqrt(n) regardless of dimensionality — this is why MC beats grid methods in high dimensions.