Abstract: We propose and analyze a novel Multi-Index Monte Carlo (MIMC) method for weak approximation of stochastic models that are described in terms of di􏰠erential equations either driven by random measures or with random coe􏰢cients. The MIMC method is both a stochas- tic version of the combination technique introduced by Zenger, Griebel and collaborators and an extension of the Multilevel Monte Carlo (MLMC) method 􏰡rst described by Heinrich and Giles. Inspired by Giles's seminal work, we use in MIMC high-order mixed di􏰠erences instead of using 􏰡rst-order di􏰠erences as in MLMC to reduce the variance of the hierarchical di􏰠erences dramati- cally. This in turn yields new and improved complexity results, which are natural generalizations of Giles's MLMC analysis and which increase the domain of the problem parameters for which we achieve the optimal convergence, O(tol−2). Moreover, in MIMC, the rate of increase of re- quired memory with respect to tol is independent of the number of directions up to a logarithmic term which allows far more accurate solutions to be calculated for higher dimensions than what is possible when using MLMC.

We motivate the setting of MIMC by 􏰡rst focusing on a simple full tensor index set. We then propose a systematic construction of optimal sets of indices for MIMC based on properly de􏰡ned pro􏰡ts that in turn depend on the average cost per sample and the corresponding weak error and variance. Under standard assumptions on the convergence rates of the weak error, variance and work per sample, the optimal index set turns out to be the total degree (TD) type. In some cases, using optimal index sets, MIMC achieves a better rate for the computational complexity than the corresponding rate when using full tensor index sets. We also show the asymptotic normality of the statistical error in the resulting MIMC estimator and justify in this way our error estimate, which allows both the required accuracy and the con􏰡dence level in our computational results to be prescribed. Finally, we include numerical experiments involving a partial di􏰠erential equation posed in three spatial dimensions and with random coe􏰢cients to substantiate the analysis and illustrate the corresponding computational savings of MIMC.

Bibliography: Abdul-Lateef Haji-Ali, Fabio Nobile, Raul Tempone, Multi Index MonteCarlo: When Sparsity Meets Sampling​, accepted for publication in Numerische Mathematik, May 2015.​