Multilevel Monte Carlo for SDEs with Random Bits

In this talk we will present results concerning the approximation of expectations $\mathrm{E}(f(X))$ for $X$ being the solution process of a system of SDEs, under standard regularity assumptions, and Lipschitz-continuous (path-dependent) functionals $f \colon C([0,1],\R^d) \to \R$. We consider (restricted) Monte Carlo algorithms which may only use random bits, i.e., uniform distributions on $\{0,1\}$ instead of random numbers from $[0,1]$. This approach corresponds to the only source of randomness accessible on state of the art hardware accelerators like FPGAs (Field Programmable Gate Arrays). On one hand, we construct and analyze a multilevel Monte Carlo algorithm for which we establish an upper bound for the computational cost and an upper error bound. We are able to show, that we have the same (weak) order of convergence as in the case of random numbers. On the other hand we investigate numerically the behaviour of this algorithm for particular SDEs. A key problem in the analysis is the quantization of distributions based on random bits. This random bit approximation problem will be introduced and main results in the above context will be presented. Moreover, these results will be compared to classical quantization results.