Convergence rates for adaptive weak approximation of stochastic differential equations

Abstract. Convergence rates of adaptive algorithms for weak approximations of Ito ̂ stochastic differential equations are proved for the Monte Carlo Euler method. Two algorithms based either on optimal stochastic time steps or opti-mal deterministic time steps are studied. The analysis of their computational complexity combines the error expansions with a posteriori leading order term introduced in [A. Szepessy, R. Tempone and G. Zouraris, Comm. Pure and Appl. Math., 54, 1169-1214, 2001] and an extension of the convergence re-sults for adaptive algorithms approximating deterministic ordinary differential equations, derived in [K-S. Moon, A. Szepessy, R. Tempone and G. Zouraris, Convergence rates for adaptive approximation of ordinary differential equa-tions, to appear Numer. Math.]. The main step in the extension is the proof of the almost sure convergence of the error density. Both adaptive algorithms are proven to stop with asymptotically optimal number of steps up to a prob-lem independent factor defined in the algorithm. Numerical examples illustrate the behavior of the adaptive algorithms, motivating when stochastic and de-terministic adaptive time steps are more efficient than constant time steps and when adaptive stochastic steps are more efficient than adaptive deterministic steps. 1. Introduction to Adaptive Algorithm