Multilevel Monte Carlo and cost theorem

Fix a refinement factor $M\in \mathbb{N}$ with $M\ge 2$, a base scale $T>0$, and a finite level $L\in \mathbb{N}\cup \{0\}$. The geometric mesh widths are $h_{\mathrm{\ell }}=T{M}^{-\mathrm{\ell }}$ for $0\le \mathrm{\ell }\le L$. Let $P$ be a real random variable with $\mathbb{E}\mathrm{\mid }P\mathrm{\mid }<\mathrm{\infty }$, and for each $\mathrm{\ell }$ let $P_{\mathrm{\ell }}$ be a real random variable with $\mathbb{E}[P_{\mathrm{\ell }}^2]<\mathrm{\infty }$.

At level $0$, set ${\mathrm{\Delta }}_0=P_0$. At each level $\mathrm{\ell }\ge 1$, choose a joint law for a pair $(P_{\mathrm{\ell }}^{\mathrm{f}},P_{\mathrm{\ell }-1}^{\mathrm{c}})$ whose marginals are the laws of $P_{\mathrm{\ell }}$ and $P_{\mathrm{\ell }-1}$, respectively. Such a joint law is a coupling of the two levels. Define the correction ${\mathrm{\Delta }}_{\mathrm{\ell }}=P_{\mathrm{\ell }}^{\mathrm{f}}-P_{\mathrm{\ell }-1}^{\mathrm{c}}$. This construction gives $\mathbb{E}{\mathrm{\Delta }}_{\mathrm{\ell }}=\mathbb{E}{P}_{\mathrm{\ell }}-\mathbb{E}{P}_{\mathrm{\ell }-1}$.

For each level choose a positive integer $N_{\mathrm{\ell }}$ and take ${\mathrm{\Delta }}_{\mathrm{\ell },1},\dots ,{\mathrm{\Delta }}_{\mathrm{\ell },N_{\mathrm{\ell }}}$ to be independent copies of ${\mathrm{\Delta }}_{\mathrm{\ell }}$. Require the complete sample blocks from distinct levels to be independent. Write ${\bar{\mathrm{\Delta }}}_{\mathrm{\ell }}=N_{\mathrm{\ell }}^{-1}{\sum }_{i=1}^{N_{\mathrm{\ell }}}{\mathrm{\Delta }}_{\mathrm{\ell },i}$. The finite-level multilevel Monte Carlo estimator is ${\widehat{\mu }}_{L,\mathbf{N}}={\sum }_{\mathrm{\ell }=0}^L{\bar{\mathrm{\Delta }}}_{\mathrm{\ell }}\mathrm{.}$ All corrections have finite second moments because each level approximation does. The shared randomness inside one fine/coarse pair is what can reduce the correction variance; the estimator still uses independent sample blocks across levels.

The definition makes no claim that a coupling is optimal, that the bias or correction variance has a particular rate, or that a data-dependent stopping rule reliably estimates the remaining bias.

Use the finite hierarchy and estimator of Geometric MLMC hierarchy and coupled corrections. Put $V_{\mathrm{\ell }}=\mathrm{Var}({\mathrm{\Delta }}_{\mathrm{\ell }})$. Then $\mathbb{E}{\widehat{\mu }}_{L,\mathbf{N}}=\mathbb{E}{P}_L,\mathrm{Var}({\widehat{\mu }}_{L,\mathbf{N}})={\sum }_{\mathrm{\ell }=0}^L\frac{V_{\mathrm{\ell }}}{N_{\mathrm{\ell }}},$ and the mean square error for the target $\mathbb{E}P$ is exactly $\mathbb{E}[({\widehat{\mu }}_{L,\mathbf{N}}-\mathbb{E}P{)}^2]={\sum }_{\mathrm{\ell }=0}^L\frac{V_{\mathrm{\ell }}}{N_{\mathrm{\ell }}}+(\mathbb{E}{P}_L-\mathbb{E}P{)}^2\mathrm{.}$

Let $M\ge 2$ be an integer, $T>0$, and $h_{\mathrm{\ell }}=T{M}^{-\mathrm{\ell }}$. Let $P$ be an integrable real target. Suppose we are given an infinite compatible hierarchy: for every $\mathrm{\ell }\ge 0$ a square-integrable level approximation $P_{\mathrm{\ell }}$, and for every $\mathrm{\ell }\ge 1$ a fixed coupling of the laws of $P_{\mathrm{\ell }}$ and $P_{\mathrm{\ell }-1}$. Define ${\mathrm{\Delta }}_0=P_0$ and, under each coupling, ${\mathrm{\Delta }}_{\mathrm{\ell }}=P_{\mathrm{\ell }}^{\mathrm{f}}-P_{\mathrm{\ell }-1}^{\mathrm{c}}$. For each finite $L$, use the first $L+1$ levels and their couplings, with independent sample blocks across levels, as in Geometric MLMC hierarchy and coupled corrections. Suppose there are constants $C_b,C_v,C_c>0$ and exponents $\alpha \ge \frac{1}{2}$ and $\beta >0$ such that, for every $\mathrm{\ell }\ge 0$, $\mathrm{\mid }\mathbb{E}{P}_{\mathrm{\ell }}-\mathbb{E}P\mathrm{\mid }\le C_b{h}_{\mathrm{\ell }}^{\alpha },\mathrm{Var}({\mathrm{\Delta }}_{\mathrm{\ell }})\le C_v{h}_{\mathrm{\ell }}^{\beta },$ and the work for one level-$\mathrm{\ell }$ correction sample is at most $C_c{h}_{\mathrm{\ell }}^{-1}$. For every sufficiently small $ϵ>0$, there are a finite level $L$ and positive integer sample counts $N_0,\dots ,N_L$ for which the estimator of Geometric MLMC hierarchy and coupled corrections satisfies $\mathbb{E}[({\widehat{\mu }}_{L,\mathbf{N}}-\mathbb{E}P{)}^2]\le {ϵ}^2$ and its total work has the following upper bounds, with constants independent of $ϵ$: $\{\begin{array}{ll}O({ϵ}^{-2}),& \beta >1,\\ O\text{\hspace{0.17em}⁣}({ϵ}^{-2}(\log {ϵ}^{-1}{)}^2),& \beta =1,\\ O\text{\hspace{0.17em}⁣}\left({ϵ}^{-2-(1-\beta )\mathrm{/}\alpha }\right),& 0<\beta <1.\end{array}$ This is an upper bound under the three rate assumptions; it does not assert a matching lower bound or that the rates hold for a particular discretization.

Assume the Axiom of Choice. Use the autonomous SDE and Euler scheme contract of Euler–Maruyama strong rate under Higham–Mao–Stuart hypotheses: finite-dimensional state and Brownian noise, $C^1$ drift and diffusion, a one-sided Lipschitz drift, globally Lipschitz diffusion, polynomial local-Lipschitz drift, and the stipulated uniform moments of every order for the exact solution and Euler step and interpolation processes. In particular, retain that theorem's all-moment premise; an $L^2$ initial condition alone is not a substitute.

Fix $0<T\le 1$, an integer $M\ge 2$, and for every $\mathrm{\ell }\ge 0$ set $h_{\mathrm{\ell }}=T{M}^{-\mathrm{\ell }}$ and $P_{\mathrm{\ell }}=\phi (Y_T^{h_{\mathrm{\ell }}})$, for a globally Lipschitz real payoff $\phi$ with constant $L_{\phi }$. These levels of the same SDE give the infinite compatible family required by MLMC cost complexity under bias, variance, and work rates, with target $\mathbb{E}\phi (X_T)$. At each level pair, use the same initial value and Brownian path for the fine and coarse Euler paths, summing the $M$ fine Brownian increments to form each coarse increment. Use independent sample blocks across levels as in Geometric MLMC hierarchy and coupled corrections. For $\mathrm{\ell }\ge 1$, the coupled correction variance is $O(h_{\mathrm{\ell }})$; the finest-level payoff bias is $O(h_L^{1\mathrm{/}2})$; and one coupled path-pair sample costs $O(h_{\mathrm{\ell }}^{-1})$. At level $0$, $P_0\in L^2$ by the all-moment premise and the Lipschitz payoff, and one Euler path has finite work. Since $h_0=T$ is fixed, enlarge the rate constants to include $\mathrm{Var}(P_0)=O(h_0)$ and the level-zero work $O(h_0^{-1})$. Hence $(\alpha ,\beta )=(1\mathrm{/}2,1)$ and the MLMC estimator has MSE at most ${ϵ}^2$ with work $O({ϵ}^{-2}(\log {ϵ}^{-1}{)}^2)$.

Assume the Axiom of Choice and the exact finite-$L^2$ SDE, initial-value, coefficient, and nested-grid hypotheses of Shared-Brownian Euler level correction rates, with $0<T\le 1$, fixed integer $M\ge 2$, and a globally Lipschitz payoff $\phi$. For every $\mathrm{\ell }\ge 0$, set $h_{\mathrm{\ell }}=T{M}^{-\mathrm{\ell }}$ and $P_{\mathrm{\ell }}=\phi (Y_T^{h_{\mathrm{\ell }}})$ for this same SDE, with target $\mathbb{E}\phi (X_T)$. These levels give the infinite compatible family required by MLMC cost complexity under bias, variance, and work rates. The finite-$L^2$ contract here is the globally state-Lipschitz and linear-growth coefficient condition, the half-Hölder time modulus, an adapted initial value independent of future Brownian increments, and $\mathbb{E}\mathrm{\mid }{X}_0{\mathrm{\mid }}^2<\mathrm{\infty }$. With shared Brownian increments within each fine/coarse pair and independent sample blocks across levels, the strong-route rates are $(\alpha ,\beta )=(1\mathrm{/}2,1)$ and the MLMC work is $O({ϵ}^{-2}(\log {ϵ}^{-1}{)}^2)$.

If, in addition, $\phi$ is bounded and its backward value function $u(t,x)=\mathbb{E}[\phi (X_T^{t,x})]$ solves the backward equation with the mixed derivative and polynomial-growth bounds and the $p\ge 2q+8$ moment condition in Euler–Maruyama weak order one under backward regularity, then the weak bias rate is $\alpha =1$ while $\beta =1$ and the same logarithmic work bound follows. In the strong branch $P_0\in L^2$ by the finite-$L^2$ scheme moment bound and the Lipschitz payoff; in the weak branch it is bounded. The level-zero path has finite work, and because $h_0=T$ is fixed, enlarging the rate constants makes its variance and work satisfy the same bounds. This second branch is conditional on backward regularity; Lipschitz continuity of $\phi$ alone does not imply it.