Title: Multilevel nested simulation for efficient risk estimation,
Abstract: We investigate the problem of computing a nested expectation of the form
$\mathbb{P}[\mathbb{E}[X|Y]
\!\geq\!0]\!=\!\mathbb{E}[\textrm{H}(\mathbb{E}[X|Y])]$ where $\textrm{H}$ is
the Heaviside function. This nested expectation appears, for example, when
estimating the probability of a large loss from a financial portfolio. We
present a method that combines the idea of using Multilevel Monte Carlo (MLMC)
for nested expectations with the idea of adaptively selecting the number of
samples in the approximation of the inner expectation, as proposed by (Broadie
et al., 2011). We propose and analyse an algorithm that adaptively selects the
number of inner samples on each MLMC level and prove that the resulting MLMC
method with adaptive sampling has an $\mathcal{O}\left(
\varepsilon^{-2}|\log\varepsilon|^2 \right)$ complexity to achieve a root
mean-squared error $\varepsilon$. The theoretical analysis is verified by
numerical experiments on a simple model problem. We also present a stochastic
root-finding algorithm that, combined with our adaptive methods, can be used to
compute other risk measures such as Value-at-Risk (VaR) and Conditional
Value-at-Risk (CVaR), with the latter being achieved with
$\mathcal{O}\left(\varepsilon^{-2}\right)$ complexity.