Adaptive Multilevel Monte Carlo for Probabilities

We consider the numerical approximation of P[G ∊ Ω], where the d-dimensional random variable G cannot be sampled directly, but there is a hierarchy of increasingly accurate approximations {G _ℓ} _ℓ∊ _N which can be sampled. The cost of standard Monte Carlo estimation scales poorly with accuracy in this setup since it compounds the approximation and sampling cost. A direct application of multilevel Monte Carlo (MLMC) improves this cost scaling slightly, but returns suboptimal computational complexities since estimation of the probability involves a discontinuous functional of G _ℓ. We propose a general adaptive framework which is able to return the MLMC complexities seen for smooth or Lipschitz functionals of G _ℓ. Our assumptions and numerical analysis are kept general allowing the methods to be used for a wide class of problems. We present numerical experiments on nested simulation for risk estimation, where G = E [X| Y] is approximated by an inner Monte Carlo estimate. Further experiments are given for digital option pricing, involving an approximation of a d-dimensional SDE.