Multilevel Monte Carlo for SDE Payoffs

Why Use Multiple Time Resolutions?

Simulating an SDE on a fine time grid can reduce discretization error, but each simulated path is more expensive. Multilevel Monte Carlo (MLMC) uses a different idea: estimate the payoff on a fine grid by combining many inexpensive coarse simulations with fewer simulations of corrections between successive grids. The corrections are constructed by coupling the fine and coarse paths, so their differences often have smaller variance than either payoff alone.

Fix a filtered probability space \((\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge0},\mathbb{P})\) carrying a standard Brownian motion \(B_t\). Consider the scalar SDE \(dX_t=\mu(t,X_t)\,dt+\sigma(t,X_t)\,dB_t\), with initial value \(X_0\). The drift is \(\mu\), and the diffusion coefficient is \(\sigma\). Its integral form is \(X_t=X_0+\int_0^t\mu(s,X_s)\,ds+\int_0^t\sigma(s,X_s)\,dB_s\). The stochastic integral here is the Ito integral: its integrand is progressively measurable and belongs to \(\mathcal{L}^2\) on each finite interval, meaning \(\mathbb{E}\int_0^T H_s^2\,ds<\infty\). In particular, assume \(\sigma(s,X_s)\) satisfies this condition for the interval being considered.

A standard sufficient setup for existence of a unique strong solution with finite-time second moments is that the coefficients are suitably measurable in time, globally Lipschitz in the state variable, and of linear growth, and that \(X_0\) is \(\mathcal{F}_0\)-measurable with \(\mathbb{E}[X_0^2]<\infty\). The second-moment assumption on \(X_0\) matters: coefficient conditions alone do not imply finite second moments when the initial value has infinite second moment. We use an Euler–Maruyama approximation, defined by \(X_{n+1}=X_n+\mu(t_n,X_n)h+\sigma(t_n,X_n)\Delta B_n\), where \(\Delta B_n=B_{t_{n+1}}-B_{t_n}\). The estimates below require the simulated payoffs to have finite second moments.

Nested Grids and Coupled Corrections

Choose a base step \(h_0=T/M\), where \(M\) is a positive integer, and use grids with step sizes \(h_\ell=h_0\,2^{-\ell}\), for levels \(\ell=0,1,\ldots,L\). A fine grid at level \(\ell\ge1\) has two steps for every coarse step at level \(\ell-1\). Couple the simulations by constructing each coarse Brownian increment as the sum of its two fine increments. For example, if the fine increments are \(\Delta B_{2j}\) and \(\Delta B_{2j+1}\), the corresponding coarse increment is \(\Delta B_{2j}+\Delta B_{2j+1}\). This sum has the Brownian increment distribution over the coarse interval.

Let \(P_\ell\) be the payoff calculated from the level-\(\ell\) numerical path. For a terminal payoff, this may be \(g(X_T^{(\ell)})\); for a path-dependent payoff it may depend on several simulated values. In every difference \(P_\ell-P_{\ell-1}\), use the coupled paths just described. Although the two payoff values share Brownian increments, each marginal payoff has the same distribution as a simulation performed on its own grid.

The expectation targeted by this finite-level estimator is \(\mathbb{E}[P_L]\), the expected payoff of the level-\(L\) numerical approximation. It is not automatically the exact continuous-time expectation \(\mathbb{E}[P]\). The difference between those expectations is time-discretization bias; increasing the sample counts reduces sampling error, not discretization bias.

The Telescoping Identity and Its Estimator

Proof. The identity \(Y_0=P_0\) and \(Y_\ell=P_\ell-P_{\ell-1}\) gives, on every outcome on which the payoffs are defined, \(\sum_{\ell=0}^{L}Y_\ell=P_0+(P_1-P_0)+\cdots+(P_L-P_{L-1})=P_L\). Finite expectations allow expectations to pass through this finite sum. The marginal distributions of the coupled fine and coarse simulations are the level-\(\ell\) and level-\((\ell-1)\) distributions, so taking expectations gives \(\mathbb{E}[Y_\ell]=\mathbb{E}[P_\ell]-\mathbb{E}[P_{\ell-1}]\). Summing these differences yields \(\mathbb{E}[P_L]\). For each level, the sample average has expectation \(\mathbb{E}[Y_\ell]\), by linearity of expectation. Summing the sample averages therefore gives \(\mathbb{E}[\widehat{P}_L]=\sum_{\ell=0}^L\mathbb{E}[Y_\ell]=\mathbb{E}[P_L]\). This proves unbiasedness for the finest chosen grid, not for the exact SDE payoff unless that payoff expectation equals \(\mathbb{E}[P_L]\). \(\square\)

Variance, Cost, and Sample Allocation

Write \(v_\ell=\operatorname{Var}(Y_\ell)\) and let \(c_\ell>0\) be the expected computational cost of one sample on level \(\ell\). For independent samples within each level and independent sampling across levels, the variance of the estimator is \(\operatorname{Var}(\widehat{P}_L)=\sum_{\ell=0}^{L}v_\ell/N_\ell\). The expected total cost is \(\sum_{\ell=0}^{L}c_\ell N_\ell\). Coupling matters because the correction variance is \(\operatorname{Var}(P_\ell-P_{\ell-1})=\operatorname{Var}(P_\ell)+\operatorname{Var}(P_{\ell-1})-2\operatorname{Cov}(P_\ell,P_{\ell-1})\). A positive covariance from shared increments reduces the variance that must be estimated at the finer levels.

Proof. For any positive real counts \(N_\ell\), apply Cauchy–Schwarz to the vectors with entries \(\sqrt{v_\ell/N_\ell}\) and \(\sqrt{c_\ell N_\ell}\). This gives \(\big(\sum_{\ell=0}^{L}\sqrt{v_\ell c_\ell}\big)^2\le\big(\sum_{\ell=0}^{L}v_\ell/N_\ell\big)\big(\sum_{\ell=0}^{L}c_\ell N_\ell\big)\). If the variance is at most \(\varepsilon^2\), the total cost is therefore at least \(\varepsilon^{-2}(\sum_{\ell=0}^{L}\sqrt{v_\ell c_\ell})^2\). For the proposed counts, the variance is \(\sum_\ell v_\ell/(A\sqrt{v_\ell/c_\ell})=A^{-1}\sum_\ell\sqrt{v_\ell c_\ell}=\varepsilon^2\). Their cost is \(A\sum_\ell\sqrt{v_\ell c_\ell}=\varepsilon^{-2}(\sum_\ell\sqrt{v_\ell c_\ell})^2\), attaining the lower bound. Equality in Cauchy–Schwarz requires the two vectors to be proportional, which gives \(N_\ell\) proportional to \(\sqrt{v_\ell/c_\ell}\). Hence this allocation is optimal for the continuous problem. Actual sample counts must be positive integers; rounding up the continuous counts ensures the sampling variance does not increase, though the rounded allocation need not be exactly cost-optimal among integers. \(\square\)

If some correction has zero variance, it is constant almost surely and contributes no sampling variance; the positive-variance formula is applied to the other levels. A constant correction still has an expectation that must be accounted for, either by evaluating it or by sampling it at least once. In practice, \(v_\ell\) and \(c_\ell\) are estimated from pilot simulations, and allocations are adjusted using those estimates.

Common Pitfall: Simulating the Two Levels Independently

Forgetting the coupling can make a correction look much noisier than it needs to be. Consider \(dX_t=dB_t\), \(X_0=0\), \(T=1\), with payoff \(P=X_1\). Euler–Maruyama gives \(P_0=\Delta B\) on a one-step grid. On a two-step grid, the fine payoff is \(P_1=\Delta B_1+\Delta B_2\), where the two increments are independent with variance \(\tfrac12\) each. Under the required coupling, the coarse increment is \(\Delta B=\Delta B_1+\Delta B_2\), so \(P_1-P_0=0\) on every outcome and the correction variance is zero.

Wrong calculation: if the coarse and fine payoffs are instead simulated independently, one might calculate \(\operatorname{Var}(P_1-P_0)=\operatorname{Var}(P_1)+\operatorname{Var}(P_0)=1+1=2\). That is the variance for independent simulations, not the variance of the coupled MLMC correction. With coupling, the two payoffs are identical and their covariance is \(1\), so the correct calculation is \(1+1-2(1)=0\). This example also shows why marginally correct simulations alone do not give an efficient multilevel estimator: the dependence between paired levels is essential.

MLMC is useful when fine-grid corrections are inexpensive to estimate in aggregate because they have low variance, while coarse paths cost less per sample. Its efficiency depends on both features: a slowly decreasing correction variance can limit the benefit, and a rapidly increasing fine-grid cost can make fine levels expensive even when their variances are small. The telescoping identity guarantees the target expectation for a chosen finest grid; the allocation formula addresses sampling cost for a chosen sampling-variance target. Choosing the finest grid to control discretization bias is a separate decision.