Monte Carlo method Study Guide

📖 Core Concepts Monte Carlo method – computational algorithm that solves deterministic problems by repeatedly sampling random inputs and aggregating the results. Random sampling – draws from a probability distribution (often uniform) to explore the input space. Expected value estimation – the average of many independent simulation outputs approximates the true expected value. Monte Carlo integration – treats an integral as an expectation; the integral ≈ sample mean of the integrand evaluated at random points. Markov Chain Monte Carlo (MCMC) – builds a Markov chain whose stationary distribution equals the target distribution; samples become asymptotically correct. Importance sampling – bias the sampling distribution toward regions where the integrand is large to reduce variance. Quasi‑Monte Carlo – replaces pseudo‑random numbers with low‑discrepancy sequences (e.g., Sobol) for faster convergence. --- 📌 Must Remember Uniformity matters – non‑uniform sampling in simple estimators (e.g., π) yields poor results. Error vs. sample size – MC error ∝ $1/\sqrt{N}$; quadrupling $N$ halves the error, independent of dimension. Sample‑size formula (known variance): $$n = \frac{z^{2}\,s^{2}}{\epsilon^{2}}$$ where $z$ = z‑score for confidence level, $s^{2}$ = estimated variance, $\epsilon$ = tolerated error. Bounded‑result formula (range known, half‑range $b$): $$n = \left(\frac{z\,b}{\epsilon}\right)^{2}$$ Pseudorandom generators must have long periods, pass statistical tests, and exhibit low autocorrelation. MCMC convergence – ergodic theorem guarantees empirical distribution → stationary distribution as iterations → ∞. Parallelism – MC simulations are “embarrassingly parallel”; speed‑up is linear with cores/GPUs when work is split evenly. --- 🔄 Key Processes Basic Monte Carlo Estimation Define input domain & probability distribution. Generate $N$ independent random samples. Compute deterministic output for each sample. Average outputs → estimator of the desired quantity. Simple Monte Carlo Sample‑Size Determination Choose confidence level → obtain $z$. Run a pilot run → estimate variance $s^{2}$. Plug into $n = (z^{2}s^{2})/\epsilon^{2}$ (or bounded formula). Importance Sampling Select proposal distribution $q(x)$ that mimics shape of integrand $f(x)$. For each sample $xi \sim q$, weight by $wi = f(xi)/q(xi)$. Estimate integral as $\frac{1}{N}\sum wi$. Metropolis–Hastings (MCMC) Propose move $x' \sim Q(x \to x')$. Compute acceptance probability $\alpha = \min\left(1,\frac{\pi(x')Q(x'\to x)}{\pi(x)Q(x\to x')}\right)$. Accept $x'$ with prob. $\alpha$, else stay at $x$. Repeat → chain converges to target $\pi(x)$. Monte‑Carlo Tree Search (MCTS) Select: traverse tree using a policy (e.g., UCB). Expand: add a new child node. Simulate: run a random playout to a terminal state. Back‑propagate: update win/visit counts up the path. --- 🔍 Key Comparisons Monte Carlo vs. Deterministic “What‑If” Monte Carlo: samples entire probability distributions → yields full output distribution, captures tail events. Deterministic: single best‑guess values → only a few scenario outcomes, may miss rare but critical events. Pseudorandom vs. True Random Pseudorandom: deterministic algorithm, repeatable, fast; quality judged by period & statistical tests. True random: derived from physical processes; not needed for most simulations; slower, non‑repeatable. Standard MC vs. Quasi‑Monte Carlo Standard MC: uses independent random points → convergence $O(N^{-1/2})$. Quasi‑MC: low‑discrepancy sequences → often faster convergence (≈ $O(N^{-1})$) for smooth integrands. Importance Sampling vs. Simple MC Importance: samples where integrand is large → lower variance if proposal is well‑chosen. Simple MC: uniform sampling → easy but may waste effort on low‑impact regions. --- ⚠️ Common Misunderstandings “More samples always improve accuracy linearly.” Accuracy improves as $\sqrt{N}$, not $N$; diminishing returns are real. “Any random number generator works equally well.” Poor generators (short period, high correlation) can bias results, especially in high‑dimensional or long‑run simulations. “MCMC samples are independent.” Consecutive MCMC draws are correlated; effective sample size is smaller than raw count. “Quasi‑Monte Carlo eliminates randomness.” It replaces randomness with deterministic low‑discrepancy points; still an approximation, not exact. “Monte Carlo integration works for any integrand without tricks.” Highly peaked or rare‑event integrands need importance sampling or stratification to avoid huge variance. --- 🧠 Mental Models / Intuition “Random walk to explore a landscape.” – Imagine a hiker taking random steps; the more steps taken, the better the picture of the terrain’s average height. “Weighting the crowd.” – In importance sampling, think of giving louder speakers (high‑weight regions) a microphone so their opinions dominate the average. “Parallel kitchen.” – Each CPU/GPU core is a chef preparing the same recipe on separate ingredients; the final dish is the average of all plates. --- 🚩 Exceptions & Edge Cases Bounded results – When every simulation output lies in $[L, U]$, use the bounded‑result formula; otherwise the variance‑based formula is needed. Heavy‑tailed distributions – Variance may be infinite; standard $n$ formula fails → use robust estimators or transform the problem. Low‑discrepancy sequences – Lose their advantage when the integrand is highly discontinuous or noisy. MCMC convergence diagnostics – Without burn‑in removal or autocorrelation assessment, early samples can bias estimates. --- 📍 When to Use Which Simple expected‑value estimation → plain Monte Carlo with uniform pseudorandom numbers. High‑dimensional integrals → Monte Carlo (standard or quasi‑Monte Carlo) rather than deterministic quadrature. Integrand has sharp peaks → Importance sampling or VEGAS adaptive algorithm. Need samples from a complex distribution → MCMC (Metropolis–Hastings, Gibbs) or Sequential Monte Carlo. Optimization over huge search spaces → Monte Carlo‑based stochastic search (e.g., simulated annealing) or Monte‑Carlo tree search for game trees. Real‑time or hardware‑constrained environments → Low‑discrepancy quasi‑Monte Carlo for faster convergence with fewer samples. --- 👀 Patterns to Recognize $1/\sqrt{N}$ error decay appears in any plain MC estimator. Variance reduction often shows up as a factor of the weight variance; smaller weight variance → tighter confidence intervals. Correlation in MCMC chains → autocorrelation plots that decay slowly indicate poor mixing. Stratified/recursive sampling → look for repeated subdivision of the domain (e.g., VEGAS grids). Monte Carlo tree search – repeated “select‑expand‑simulate‑back‑propagate” loops in game‑AI problems. --- 🗂️ Exam Traps Choosing the wrong $z$‑score – mixing up 95 % (z≈1.96) with 90 % (z≈1.64) leads to under‑/over‑estimating $n$. Using variance formula when results are bounded – the bounded‑result formula gives a tighter guarantee; using the variance formula can over‑estimate $n$. Assuming independence in MCMC – exam questions may present an MCMC estimate and ask for effective sample size; forgetting correlation yields an inflated precision claim. Confusing quasi‑Monte Carlo with true randomness – a distractor might claim quasi‑MC is “random”; the correct answer emphasizes deterministic low‑discrepancy nature. “More dimensions always mean worse MC performance” – while deterministic methods suffer from the curse of dimensionality, MC error is dimension‑independent; a common wrong answer states MC error grows with dimension. ---