Random bit multilevel algorithms for stochastic differential equations

DOI10.1016/J.JCO.2019.01.002MaRDI QIDQ2274401zbMATH OpenOpenAlexWikidataFDO

Authors Mike Giles, Mario Hefter, Lukas Mayer, Klaus Ritter

Publication date 19 September 2019

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.10623

zbMATH Keywords

multilevel Monte Carlo algorithmsrandom bitsstochastic differential equations

Mathematics Subject Classification ID

Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Monte Carlo methods (65C05) Numerical solutions to stochastic differential and integral equations (65C30)

Abstract: We study the approximation of expectations $E(f(X))$ for solutions $X$ of SDEs and functionals $fcolonC([0,1],R^r)oR$ by means of restricted Monte Carlo algorithms that may only use random bits instead of random numbers. We consider the worst case setting for functionals $f$ from the Lipschitz class w.r.t. the supremum norm. We construct a random bit multilevel Euler algorithm and establish upper bounds for its error and cost. Furthermore, we derive matching lower bounds, up to a logarithmic factor, that are valid for all random bit Monte Carlo algorithms, and we show that, for the given quadrature problem, random bit Monte Carlo algorithms are at least almost as powerful as general randomized algorithms.

Recommendations

• An adaptive random bit multilevel algorithm for SDEs
• Random bit quadrature and approximation of distributions on Hilbert spaces
• scientific article; zbMATH DE number 2186130
• Constructive Quantization and Multilevel Algorithms for Quadrature of Stochastic Differential Equations
• Multi-level Monte Carlo methods with the truncated Euler-Maruyama scheme for stochastic differential equations

Cites work

• Coin Tossing Algorithms for Integral Equations and Tractability
• Deterministic and stochastic error bounds in numerical analysis
• scientific article; zbMATH DE number 3967784 (Why is no real title available?)
• scientific article; zbMATH DE number 2051207 (Why is no real title available?)
• scientific article; zbMATH DE number 3390215 (Why is no real title available?)
• Improving multilevel Monte Carlo for stochastic differential equations with application to the Langevin equation
• Infinite-dimensional quadrature and approximation of distributions
• Mixed precision multilevel Monte Carlo algorithms for reconfigurable computing systems
• Multilevel path simulation for weak approximation schemes with application to Lévy-driven SDEs
• Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes
• Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• Quantum complexity of integration
• The Monte Carlo Algorithm with a Pseudorandom Generator
• Uniform decomposition of probability measures: quantization, clustering and rate of convergence

Cited in

(11)

• Random bit quadrature and approximation of distributions on Hilbert spaces
• Asymptotics of one-dimensional Lévy approximations
• Best finite constrained approximations of one-dimensional probabilities
• An adaptive random bit multilevel algorithm for SDEs
• On the Power of Restricted Monte Carlo Algorithms
• Constructive Quantization and Multilevel Algorithms for Quadrature of Stochastic Differential Equations
• Analysis of nested multilevel Monte Carlo using approximate normal random variables
• Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms
• Rounding error using low precision approximate random variables
• Approximating inverse cumulative distribution functions to produce approximate random variables
• Error estimates for deterministic empirical approximations of probability measures

This page was built for publication: Random bit multilevel algorithms for stochastic differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274401)