Monte Carlo Methods
Sampling, importance sampling, MCMC, variance reduction
You need E[f(X)] where X follows some complex distribution and f(X) is the revenue of a pricing model under uncertain market conditions. You cannot compute the integral analytically. But you can do this: sample X₁, X₂, ..., X_n from the distribution, evaluate f(X_i) for each, and average. By the law of large numbers, the average converges to E[f(X)] as n → ∞. This is Monte Carlo integration — replace an intractable integral with a sample average.
Why it works: the law of large numbers guarantees convergence. The CLT tells you the error rate: the standard error of the Monte Carlo estimate is σ/√n where σ² = Var[f(X)]. To halve the error, quadruple the sample size. The convergence rate O(1/√n) is independent of the dimension of X — unlike grid integration, which requires N^d evaluations in d dimensions. This dimension-independence is the entire reason Monte Carlo is the only tractable option for high-dimensional integration.
MCMC (Markov Chain Monte Carlo): when you cannot sample directly from the target distribution but can evaluate the density up to a normalizing constant. Metropolis-Hastings: propose a move from x to x', accept with probability min(1, p(x')/p(x)). The chain's stationary distribution is p(x). The acceptance ratio cancels the intractable normalizing constant — you never need to compute it. MCMC is the standard tool for Bayesian posterior sampling.
Importance sampling: use a proposal distribution q(x) instead of sampling from p. Reweight each sample by p(x)/q(x). The estimator is unbiased. But if q has lighter tails than p, a small number of samples get enormous weights and dominate the estimate — the effective sample size collapses. Always diagnose importance sampling with the effective sample size: ESS = (Σ w_i)² / Σ w_i². If ESS/n < 0.1, the proposal is misspecified.
NOT this. Monte Carlo is not only for simulations. Monte Carlo is the default tool for Bayesian posterior inference (MCMC samples from the posterior), for dropout uncertainty estimation (run the model k times with dropout active and average the predictions), for model evaluation confidence intervals (bootstrap resampling is Monte Carlo over the empirical distribution), and for reinforcement learning policy gradient estimation (sample trajectories to estimate E[reward]). Anywhere you see an expectation you cannot compute analytically, Monte Carlo is the practical solution.
Key points
- Use bootstrap resampling — sampling with replacement from your dataset, repeated 1000 times — for confidence intervals on any statistic. Bootstrap requires no distributional assumption and works for complex statistics like AUC, NDCG, and precision@K where there is no analytical confidence interval formula. It is the universal fallback when you cannot derive a standard error.
- Trap: importance weights that blow up. If your proposal q(x) has lighter tails than the target p(x), some samples get enormous weights, the variance of the estimator blows up, and the effective sample size is tiny. Always compute ESS = (Σ w_i)² / Σ w_i² after importance sampling. If ESS/n < 0.1, your proposal is misspecified — use a heavier-tailed proposal or switch to MCMC.
- Diagnostic: for MCMC, check mixing with trace plots and R-hat statistics. Trace plots of sampled values over iterations should look like white noise — rapid fluctuations around a stable level. Slow drift or long autocorrelation indicates the chain is not mixing well. R-hat < 1.1 across multiple chains initialized from different starting points indicates convergence to the same stationary distribution.
Monte Carlo error scales as O(1/√n) regardless of dimension. That dimension-independence is the entire reason Monte Carlo dominates variational inference, policy gradients, and any high-dimensional expectation. Variance of the integrand — not dimension — determines how many samples you need.
Recap
- Monte Carlo = replace an intractable integral with a sample average: sample Xᵢ, average f(Xᵢ) → E[f(X)].
- Error = σ/√n, O(1/√n) and dimension-independent — halve error → quadruple samples. Why it beats grid integration (Nᵈ).
- MCMC (Metropolis-Hastings): accept x→x' with min(1, p(x')/p(x)); the ratio cancels the normalising constant.
- Importance sampling reweights by p(x)/q(x) — unbiased, but light-tailed q → a few huge weights dominate.
- Diagnose IS with ESS = (Σwᵢ)²/Σwᵢ²; ESS/n < 0.1 means the proposal is misspecified.
- MCMC mixing: trace plots like white noise, R-hat < 1.1 across chains from different starts.
- MC is everywhere: Bayesian posteriors, dropout uncertainty, bootstrap CIs, RL policy gradients — any expectation you can't solve.
Check your understanding
Q1. Estimate ∫₀¹ √x dx using Monte Carlo with n=1000 samples. Describe the algorithm and the expected error.
- A) Algorithm: (1) sample xᵢ ~ Uniform(0,1) for i=1,...,1000; (2) estimate Î = (1/1000)Σᵢ√xᵢ. True value: ∫₀¹√x dx = 2/3 ≈ 0.667. Error: SE = σ/√n, where σ² = Var(√U) = E[U] − (E[√U])² = 1/2 − 4/9 = 1/18, so SE ≈ 0.236/√1000 ≈ 0.0075. However, this specific estimator is only the standard Monte Carlo approach; the alternative hit-or-miss estimator, which samples uniformly in [0,1]×[0,1] and checks whether y ≤ √x, is strictly less efficient and gives a noticeably larger SE ≈ 0.015 for the same sample budget.
- B) Algorithm: (1) draw n=1000 points (xᵢ,yᵢ) ~ Uniform([0,1]²); (2) count hits where yᵢ ≤ √xᵢ; (3) estimate Î = hits/n. True value = 2/3. This hit-or-miss approach targets the same integral as the direct expectation estimator but is statistically less efficient, requiring more samples to reach the same accuracy. SE ≈ √(p(1−p)/n) ≈ √(0.667·0.333/1000) ≈ 0.015, roughly twice the error of the direct expectation estimator for an identical sample budget.
- C) Algorithm: (1) evaluate √xᵢ at n=1000 equally spaced points xᵢ = i/1000; (2) estimate Î = (1/1000)Σᵢ√(i/1000). This is a deterministic Riemann sum, not Monte Carlo at all — there is no randomness in the sample locations. Error here is O(1/n) rather than O(1/√n), so deterministic quadrature is strictly more accurate than Monte Carlo in a single dimension. Monte Carlo's real advantage, dimension-independence, only actually emerges once the dimensionality grows to d ≥ 3 or so.
- D) Draw Uᵢ ~ Uniform(0,1) for i=1,...,1000 and compute Î = (1/1000)Σᵢ√Uᵢ. This works because ∫₀¹√x dx = E[√U] for U~Uniform(0,1), and by LLN, Î → E[√U] as n→∞. True value: 2/3 ≈ 0.667. Expected error: SE ≈ σ/√n where σ² = Var(√U) = E[U] − (E[√U])² = 1/2 − 4/9 = 1/18, so σ ≈ 0.236 and SE ≈ 0.0075 — the estimate lands within ±0.015 (2 SE) with 95% probability. This O(1/√n) error is dimension-independent, unlike quadrature's O(n^{-k/d}).
Q2. What is importance sampling, and when is standard Monte Carlo estimation inefficient?
- A) Importance sampling is a variance reduction technique that evaluates f(x) at strategically chosen points rather than genuinely random points. Instead of sampling xᵢ ~ p, you deliberately choose evaluation points at the quantiles of p, which turns the estimator into a deterministic quadrature rule achieving O(1/n) convergence instead of Monte Carlo's usual O(1/√n). The so-called 'importance' weights w(x) = 1/p(x) simply correct for the uneven spacing between the chosen quantile points.
- B) Standard MC estimates E_p[f(x)] = (1/n)Σf(xᵢ) where xᵢ~p; this is inefficient when f(x) is nonzero only in a region p rarely samples (e.g., P(catastrophic failure)). Importance sampling introduces an easy-to-sample proposal q: E_p[f(x)] = E_q[f(x)·p(x)/q(x)], estimated as Î = (1/n)Σᵢf(xᵢ)p(xᵢ)/q(xᵢ) with xᵢ~q. The optimal q*(x) ∝ |f(x)|p(x) concentrates samples where the integrand is large, but IS can blow up to infinite variance if q has lighter tails than p·f.
- C) Importance sampling is essentially equivalent to stratified sampling: partition the sample space into strata and sample from each stratum with probability proportional to that stratum's importance weight. Standard Monte Carlo becomes inefficient specifically when the integrand is multimodal, since each mode then requires its own dedicated sample stratum to be represented well. The importance weights w(x) = p(x)/q(x) must sum exactly to n across all drawn samples for the resulting estimator to remain unbiased.
- D) Standard Monte Carlo is always statistically efficient once n is large enough, regardless of the shape of f or p. Importance sampling is instead a bias-correction technique for cases where the sampler itself introduces systematic bias — for example, when running MCMC with a non-stationary proposal distribution, or when sampling from a truncated version of the target distribution. The weights p(x)/q(x) correct for this bias by reweighting the biased samples from q to match the true target distribution p.
Q3. Which two of the following statements about MCMC convergence and burn-in are correct?
- A) Convergence formally means the total variation distance between the chain's marginal distribution at step t and the target posterior goes to zero as t→∞: ||P(θ_t∈·) − P(·|data)||_TV → 0, guaranteed under ergodicity — irreducibility and aperiodicity — of the transition kernel K(θ'|θ).
- B) Burn-in samples are discarded because they are still influenced by the arbitrary initial state θ₀ and are not yet genuine draws from the target distribution; R̂ (Gelman-Rubin), computed across multiple chains started from different points, is the standard diagnostic for how long burn-in should run.
- C) Convergence means the Metropolis-Hastings acceptance rate settles at exactly 23–44%; once the acceptance rate hits that window, all subsequent samples are guaranteed i.i.d. draws from the posterior regardless of how the chain was initialised or how correlated consecutive samples are.
- D) Convergence is achieved once the log-probability trace plot visibly plateaus, at which point the Markov chain behaves exactly like an i.i.d. sampler, so no thinning or further correlation correction between consecutive samples is ever needed.
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →