Multilevel Monte Carlo and cost theorem — Examples

Since each level is deterministic, [F1] gives ${\mathrm{\Delta }}_0=1$, ${\mathrm{\Delta }}_1=\frac{1}{2}-1=-\frac{1}{2}$, and ${\mathrm{\Delta }}_2=\frac{1}{4}-\frac{1}{2}=-\frac{1}{4}$.

Each sample mean equals its constant correction, so ${\widehat{\mu }}_{2,\mathbf{N}}=1-\frac{1}{2}-\frac{1}{4}=\frac{1}{4}=\mathbb{E}{P}_2$. Its sampling variance is zero, while [F2] gives MSE $(\frac{1}{4}-0{)}^2=\frac{1}{16}$.

With $ϵ=2^{-k}$ and $C_b=T=1$, the bias cutoff $h_L^{\alpha }\le ϵ\mathrm{/}\sqrt{2}$ requires $L\ge {\alpha }^{-1}(k+\frac{1}{2})$. Thus the strong routes with $\alpha =\frac{1}{2}$ use $L=2k+O(1)$, while the weak route with $\alpha =1$ uses $L=k+O(1)$. The meshes and level-block independence are those of [F3].

For $\mathrm{\ell }\ge 1$, the fine and coarse paths take $2^{\mathrm{\ell }}$ and $2^{\mathrm{\ell }-1}$ Euler steps. Summing pairs of fine Brownian increments forms the coarse increments in $O(2^{\mathrm{\ell }})$ operations. Under the stated fixed-dimension unit-cost model, the coupled sample therefore costs $O(2^{\mathrm{\ell }})=O(h_{\mathrm{\ell }}^{-1})$; level zero takes one Euler step and also satisfies this bound. Thus $\gamma =1$ in every branch, while [F1]–[F2] give $\beta =1$ and the logarithmic MLMC work bound $O({ϵ}^{-2}(\log {ϵ}^{-1}{)}^2)=O(2^{2k}{k}^2)$. The change in $\alpha$ changes the finest mesh count but not this complexity regime.

This is a hierarchy of the form in [F1]. The density is nonnegative on $[-1,1]$ because $c\le 1$, and its integral is $\frac{1}{2}{\int }_{-1}^1(1+cx)dx=1$. The target mean is $\mathbb{E}P=\frac{1}{2}+c\mathrm{/}4$. Writing $\delta =\sqrt{h_{\mathrm{\ell }}}$ and averaging over $S=\pm 1$ gives $\mathbb{E}{P}_{\mathrm{\ell }}=\frac{1}{2}(\mathbb{P}(X\ge -\delta )+\mathbb{P}(X\ge \delta ))=\mathbb{E}P-\frac{c{\delta }^2}{4}\mathrm{.}$ Thus $\mathrm{\mid }\mathbb{E}{P}_{\mathrm{\ell }}-\mathbb{E}P\mathrm{\mid }=c{h}_{\mathrm{\ell }}\mathrm{/}4$, so the bias exponent is $\alpha =1$.

For $\mathrm{\ell }\ge 1$, put ${\delta }_f=\sqrt{h_{\mathrm{\ell }}}$ and ${\delta }_c=\sqrt{h_{\mathrm{\ell }-1}}=\sqrt{M}{\delta }_f$. The correction ${\mathrm{\Delta }}_{\mathrm{\ell }}=P_{\mathrm{\ell }}-P_{\mathrm{\ell }-1}$ is $+1$ when $S=-1$ and ${\delta }_f\le X<{\delta }_c$, is $-1$ when $S=+1$ and $-{\delta }_c\le X<-{\delta }_f$, and is zero otherwise. Integrating the density on those two intervals and averaging over the two signs gives $\mathbb{P}({\mathrm{\Delta }}_{\mathrm{\ell }}\mathrm{\ne }0)=\frac{{\delta }_c-{\delta }_f}{2}=\frac{\sqrt{M}-1}{2}\sqrt{h_{\mathrm{\ell }}}=:p_{\mathrm{\ell }}\mathrm{.}$ The level-0 correction is bounded, so it has finite variance as well.

The two signed crossing probabilities give $\mathbb{E}{\mathrm{\Delta }}_{\mathrm{\ell }}=c(M-1)h_{\mathrm{\ell }}\mathrm{/}4$. Since ${\mathrm{\Delta }}_{\mathrm{\ell }}^2={\mathbf{1}}_{\{{\mathrm{\Delta }}_{\mathrm{\ell }}\mathrm{\ne }0\}}$, $\mathrm{Var}({\mathrm{\Delta }}_{\mathrm{\ell }})=p_{\mathrm{\ell }}-(\mathbb{E}{\mathrm{\Delta }}_{\mathrm{\ell }}{)}^2$. For $\mathrm{\ell }\ge 1$, $h_{\mathrm{\ell }}\le 1\mathrm{/}M$ and $\frac{(\mathbb{E}{\mathrm{\Delta }}_{\mathrm{\ell }}{)}^2}{p_{\mathrm{\ell }}}=\frac{c^2(M-1{)}^2{h}_{\mathrm{\ell }}^{3\mathrm{/}2}}{8(\sqrt{M}-1)}\le \frac{c^2(\sqrt{M}-1)(\sqrt{M}+1{)}^2}{8M^{3\mathrm{/}2}}\le \frac{c^2}{4}\le \frac{1}{4}\mathrm{.}$ The last inequality follows from $(\sqrt{M}-1)(\sqrt{M}+1{)}^2\le 2M^{3\mathrm{/}2}$ for $M\ge 2$. Hence $\frac{3}{4}{p}_{\mathrm{\ell }}\le \mathrm{Var}({\mathrm{\Delta }}_{\mathrm{\ell }})\le p_{\mathrm{\ell }}$, which proves the exact order $\beta =\frac{1}{2}$.

The sample evaluator uses a constant number of draws, so its cost is $O(1)\le O(h_{\mathrm{\ell }}^{-1})$ because $0<h_{\mathrm{\ell }}\le 1$. Substituting $\alpha =1$, $\beta =\frac{1}{2}$, $\gamma =1$ into [F2] gives the stated $O({ϵ}^{-5\mathrm{/}2})$ upper guarantee under that work-rate bound.

By [F1], ${\mathrm{\Delta }}_0=1$ and ${\mathrm{\Delta }}_{\mathrm{\ell }}=0$ for every $\mathrm{\ell }\ge 1$. All correction variances are zero and all sample costs satisfy the stated work bound.

By [F1], every sample mean equals its constant correction, so ${\widehat{\mu }}_{L,\mathbf{N}}=1$ for every $L$ and every sample allocation. The target mean is zero, hence the MSE is exactly $1$ and cannot be made arbitrarily small. The missing hypothesis is convergence of $\mathbb{E}{P}_L$ to $\mathbb{E}P$; here the bias remains $1$.

Since $\mathbb{E}{P}_{\mathrm{\ell }}=h_{\mathrm{\ell }}$, the finest-level bias is $h_L$, so this hierarchy has bias order $\alpha =1$. For $\mathrm{\ell }\ge 1$, the independent centered Rademacher terms have variance $1+1=2$, hence $\mathrm{Var}({\mathrm{\Delta }}_{\mathrm{\ell }})=2$ and no bound $O(h_{\mathrm{\ell }}^{\beta })$ holds for any $\beta >0$. The sample cost is exactly $h_{\mathrm{\ell }}^{-1}$.

By [F2], the MSE is $h_L^2+\frac{1}{N_0}+2{\sum }_{\mathrm{\ell }=1}^L\frac{1}{N_{\mathrm{\ell }}}\mathrm{.}$ Thus MSE at most ${ϵ}^2$ requires $h_L\le ϵ$ and $N_L\ge 2{ϵ}^{-2}$. The finest-level work alone is therefore $N_L{h}_L^{-1}\ge 2{ϵ}^{-3}$. This grows faster than ${ϵ}^{-2}(\log {ϵ}^{-1}{)}^2$, so the claimed logarithmic bound fails without a positive correction-variance decay rate.