Random Bit Multilevel Algorithms for Stochastic Differential Equations
It provides theoretical justification that random bit algorithms are almost as powerful as general randomized algorithms for this quadrature problem.
The paper studies approximation of expectations for solutions of SDEs using Monte Carlo algorithms restricted to random bits instead of random numbers, constructing a random bit multilevel Euler algorithm with matching upper and lower error bounds up to a logarithmic factor.
We study the approximation of expectations $\E(f(X))$ for solutions $X$ of SDEs and functionals $f \colon C([0,1],\R^r) \to \R$ 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.