Monte Carlo simulation — law of large numbers basis

WHY does Monte Carlo work at all?

WHAT we want: many quantities are secretly expectations.

• An integral $\int_0^1 g(x)\,dx = \mathbb{E}[g(U)]$ where $U\sim\text{Uniform}(0,1)$.
• A probability $P(A) = \mathbb{E}[\mathbf{1}_A]$ (expectation of an indicator).
• $\pi$, option prices, particle-physics cross-sections — all are averages over randomness.

WHY we can estimate them: if a quantity equals $\mathbb{E}[X]$, and we draw independent copies $X_1,\dots,X_n$ of $X$, the sample mean $\bar X_n=\frac1n\sum X_i$ should "settle down" to $\mathbb{E}[X]$. That settling-down is the Law of Large Numbers.

HOW we use it: generate random samples → plug each into the function → average. Done.

The Law of Large Numbers (derived, not dumped)

Deriving it from first principles

Step 1 — Mean of the sample mean. Why? To know what it's centered on. $\mathbb{E}[\bar X_n]=\frac1n\sum_{i=1}^n\mathbb{E}[X_i]=\frac1n\cdot n\mu=\mu.$ Why this step? Expectation is linear, so it passes through the sum. The estimator is unbiased.

Step 2 — Variance of the sample mean. Why? To measure spread shrinking. $\operatorname{Var}(\bar X_n)=\frac{1}{n^2}\operatorname{Var}\Big(\sum_{i=1}^n X_i\Big)=\frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(X_i)=\frac{1}{n^2}\cdot n\sigma^2=\frac{\sigma^2}{n}.$ Why this step? Independence lets variance of a sum equal the sum of variances (cross-covariances vanish). Pulling out $\frac1{n^2}$ uses $\operatorname{Var}(aY)=a^2\operatorname{Var}(Y)$.

Step 3 — Chebyshev's inequality. Why? It bounds "how often far from the mean" using only variance. $P\big(|\bar X_n-\mu|\ge\varepsilon\big)\le\frac{\operatorname{Var}(\bar X_n)}{\varepsilon^2}=\frac{\sigma^2}{n\varepsilon^2}.$ Why this step? Chebyshev says deviations bigger than $\varepsilon$ are rare when variance is small.

Step 4 — Take the limit. As $n\to\infty$, $\dfrac{\sigma^2}{n\varepsilon^2}\to0$. The squeeze forces the probability to 0. $\blacksquare$

The Monte Carlo estimator and its error

WHY $1/\sqrt n$ matters: to get one more decimal digit of accuracy (10× smaller error) you need 100× more samples. Dimension-independence is the payoff: this $1/\sqrt n$ holds whether $X$ is 1-D or 1000-D, which is why Monte Carlo crushes grid methods in high dimensions.

Worked Example 1 — Estimating $\pi$

WHAT: Throw random darts in the unit square $[0,1]^2$. Fraction landing inside the quarter-circle ($x^2+y^2\le1$) estimates the area $\pi/4$.

• Let $X=\mathbf{1}\{U_1^2+U_2^2\le1\}$ with $U_1,U_2\sim\text{Unif}(0,1)$.
• $\mathbb{E}[X]=P(\text{inside})=\dfrac{\text{area of quarter disk}}{\text{area of square}}=\dfrac{\pi/4}{1}=\dfrac\pi4.$ Why? Uniform points → probability = area ratio.

Estimator: $\hat\pi = 4\bar X_n$. Why ×4? Because $\bar X_n\to\pi/4$, multiply by 4 to recover $\pi$.

Error: $X$ is Bernoulli($p=\pi/4\approx0.785$), so $\sigma_g^2=p(1-p)\approx0.169$. Then $\text{SE}(\hat\pi)=4\cdot\sqrt{0.169/n}$. For $n=10^4$, SE $\approx 0.016$ — so $\hat\pi$ good to ~2 decimals. Why so slow? The fatal $1/\sqrt n$.

Worked Example 2 — A 1-D integral

Estimate $\theta=\int_0^1 e^{-x^2}\,dx$ (no elementary antiderivative).

• Write $\theta=\mathbb{E}[e^{-U^2}]$, $U\sim\text{Unif}(0,1)$. Why? $\int_0^1 g(x)\,dx=\mathbb{E}[g(U)]$ because the Uniform density is 1 on $[0,1]$.
• Draw $U_1,\dots,U_n$, compute $\hat\theta_n=\frac1n\sum e^{-U_i^2}$. Why? It's the sample mean of $g(U)$; LLN ⇒ $\to\theta\approx0.7468$.
• Standard error: estimate $\hat\sigma_g$ from the samples, report $\hat\theta_n\pm1.96\,\hat\sigma_g/\sqrt n$. Why? CLT gives the interval; honesty requires error bars.

Worked Example 3 — Forecast-then-Verify

Forecast: I run the $\pi$ estimate with $n=100$ then $n=10000$. How much should the error shrink? Ratio of $n$ is 100, so $\sqrt{100}=10$. Predict: error drops by ~10×.

Verify (typical run): $n=100 \Rightarrow$ error $\sim0.16$; $n=10000\Rightarrow$ error $\sim0.016$. ✔ Matches the $1/\sqrt n$ law. Why this matters: it lets you plan compute budget before running anything.

Common Mistakes (Steel-manned)

Active Recall

Connections

• Central Limit Theorem — gives the confidence interval / error bars.
• Chebyshev's Inequality — the engine of the WLLN proof.
• Strong Law of Large Numbers — almost-sure convergence (stronger than WLLN).
• Variance and Covariance — why independence makes variance add.
• Importance Sampling — reduces $\sigma_g$ to beat the $1/\sqrt n$ wall.
• Numerical Integration — the deterministic alternative Monte Carlo competes with.
• Bernoulli Distribution — model for indicator-based estimates like $\pi$.

Concept Map

Hinglish (regional understanding)