Adaptive Multilevel Monte Carlo for Probabilities
We consider the numerical approximation of ℙ[G∈Ω] where the d-dimensional random variable G cannot be sampled directly, but there is a hierarchy of increasingly accurate approximations {G_ℓ}_ℓ∈ℕ 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 improves this cost scaling slightly, but returns sub-optimal 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 = 𝔼[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.
READ FULL TEXT