On the complexity of computing quadrature formulas for marginal distributions of SDEs

We study the problem of approximating the distribution of the solution of a dd-dimensional system of stochastic differential equations (SDEs) at a single time point by a probability measure with finite support, i.e., by a quadrature formula with positive weights summing up to one. We consider deterministic algorithms that may use finitely many evaluations of the drift coefficient and the diffusion coefficient and we analyze their worst case behavior with respect to classes of SDEs, which are specified in terms of smoothness constraints for the coefficients of the equation. The worst case error of an algorithm is defined in terms of a metric on the space of probability measures on the state space of the solution, which is induced by a class of test functions f:Rd→Rf:Rd→R. For the definition of the worst case cost of an algorithm we either consider the size of the support of the approximating probability measure or the number of evaluations of the coefficients of the equation or the total computational cost within the real number model without pricing precomputation. We show that the order of convergence of the corresponding minimal errors is r/dr/d, min(s1,s2)/dmin(s1,s2)/d and min(r,s1,s2)/dmin(r,s1,s2)/d, respectively, up to an arbitrarily small power, where the parameters rr, s1s1 and s2s2 denote the smoothness of the test functions, the drift coefficients and the diffusion coefficients, respectively.