Monte Carlo Simulation Methods

For N i.i.d. samples, the standard error of the sample mean is σ/√N, so the error decays as O(N^(-1/2)) — independent of the dimension of the integrand.

By the Central Limit Theorem, an approximate 95% CI for the estimator is X̄ ± 1.96 · s/√N, where s is the sample standard deviation of the N payoffs.

Pseudo-random sequences mimic i.i.d. U(0,1) draws and give MC error O(N^(-1/2)). Quasi-random (low-discrepancy) sequences such as Sobol, Halton, Niederreiter are deterministic and designed to fill [0,1]^d uniformly, giving error close to O((log N)^d / N) for smooth integrands.

The star discrepancy D*_N(x₁,…,x_N) measures how uniformly a point set fills [0,1]^d. The Koksma–Hlawka inequality bounds the QMC integration error by V(f) · D*_N, where V(f) is the Hardy–Krause variation.

Smooth (low-variation) integrands have small Hardy–Krause variation, so the Koksma–Hlawka bound combined with low-discrepancy points gives near-O(1/N) convergence — far better than MC's O(N^(-1/2)). The advantage erodes in very high effective dimension or for non-smooth payoffs (e.g., barriers).

To sample X with CDF F, draw U ~ U(0,1) and set X = F^(-1)(U). Works whenever F^(-1) is available (closed-form or numerical), and is the preferred method when pairing with QMC because it preserves the low-discrepancy structure.