Single Level Importance Sampling for McKean-Vlasov Stochastic Differential Equations

This paper investigates Monte Carlo methods to estimate probabilities of rare events associated with solutions to the $d$-dimensional McKean-Vlasov stochastic differential equation. The equation is usually approximated using a stochastic interacting $P$-particle system, a set of $P$ coupled $d$-dimensional stochastic differential equations (SDEs). Importance sampling (IS) is a common technique to reduce high relative variance of Monte Carlo estimators of rare event probabilities. In the SDE context, optimal measure change is derived using stochastic optimal control theory to minimize estimator variance, which when applied to stochastic particle systems yields a $P \times d$-dimensional partial differential control equation, which is cumbersome to solve. The work in [15] circumvented this problem by a decoupling approach, producing a $d$-dimensional control PDE. Based on the decoupling approach, we develop a computationally efficient double loop Monte Carlo (DLMC) estimator. We offer a systematic approach to our DLMC estimator by providing a comprehensive error and work analysis and formulating optimal computational complexity. Subsequently, we propose an adaptive DLMC method combined with IS to estimate rare event probabilities, significantly reducing relative variance and computational runtimes required to achieve a given relative tolerance compared with standard Monte Carlo estimators without IS. The proposed estimator has $\mathcal{O}(TOL^{-4})$ computational complexity with significantly reduced constant. Numerical experiments, which are performed on the Kuramoto model from statistical physics, show substantial computational gains achieved by our estimator.