In this thesis we study a variant of the quadrature problem for stochastic differential equations (SDEs), namely the approximation of expectations E(f(X)), where X=(X(t))t∈[0,1] is the solution of an SDE and f:C([0,1],Rr)→R is a functional, mapping each realization of X into the real numbers. The distinctive feature in this work is that we consider randomized (Monte Carlo) algorithms with random bits as their only source of randomness, whereas the algorithms commonly studied in the literature are allowed to sample from the uniform distribution on the unit interval, i.e., they do have access to random numbers from [0,1]. By assumption, all further operations like, e.g., arithmetic operations, evaluations of elementary functions, and oracle calls to evaluate f are considered within the real number model of computation, i.e., they are carried out exactly. In the following, we provide a detailed description of the quadrature problem, namely we are interested in the approximation of \begin{align*} S(f) = \mathrm{E}(f(X)) \end{align*} for X being the r-dimensional solution of an autonomous SDE of the form \begin{align*} \mathrm{d}X(t) = a(X(t)) \, \mathrm{d}t + b(X(t)) \, \mathrm{d}W(t), \quad t \in [0,1], \end{align*} with deterministic initial value \begin{align*} X(0) = x_0 \in \mathbb{R}^r, \end{align*} and driven by a d-dimensional standard Brownian motion W. Furthermore, the drift coefficient a:Rr→Rr and the diffusion coefficient b:Rr→Rr×d are assumed to be globally Lipschitz continuous. For the function classes \begin{align*} F_{\infty} = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{\sup}\bigr\} \end{align*} and \begin{align*} F_p = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{L_p}\bigr\}, \quad 1 \leq p < \infty. \end{align*} we have established the following. \[\] \(\textit{Theorem 1.}\) There exists a random bit multilevel Monte Carlo (MLMC) algorithm \(M\) using \[ L = L(\varepsilon,F) = \begin{cases}\lceil{\log_2(\varepsilon^{-2}}\rceil, &\text{if} \ F = F_p,\\ \lceil{\log_2(\varepsilon^{-2} + \log_2(\log_2(\varepsilon^{-1}))}\rceil, &\text{if} \ F = F_\infty \end{cases} \] and replication numbers Nℓ=Nℓ(ε,F)={⌈(L+1)⋅2−ℓ⋅ε−2⌉,⌈(L+1)⋅2−ℓ⋅max(ℓ,1)⋅ε−2⌉,ifF=Fp,ifF=f∞ for ℓ=0,…,L, for which exists a positive constant c such that \begin{align*} \mathrm{error}(M,F) = \sup_{f \in F} \bigl(\mathrm{E}(S(f) - M(f))^2\bigr)^{1/2} \leq c \cdot \varepsilon \end{align*} and \begin{align*} \mathrm{cost}(M,F) = \sup_{f \in F} \mathrm{E}(\mathrm{cost}(M,f)) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for every ε∈]0,1/2[. \[\] Hence, in terms of the ε-complexity \begin{align*} \mathrm{comp}(\varepsilon,F) = \inf\bigl\{\mathrm{cost}(M,F) \colon M \ \text{is a random bit MC algorithm}, \mathrm{error}(M,F) \leq \varepsilon\bigr\} \end{align*} we have established the upper bound \begin{align*} \mathrm{comp}(\varepsilon,F) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for some positive constant c. That is, we have shown the same weak asymptotic upper bound as in the case of random numbers from [0,1]. Hence, in this sense, random bits are almost as powerful as random numbers for our computational problem. Moreover, we present numerical results for a non-analyzed adaptive random bit MLMC Euler algorithm, in the particular cases of the Brownian motion, the geometric Brownian motion, the Ornstein-Uhlenbeck SDE and the Cox-Ingersoll-Ross SDE. We also provide a numerical comparison to the corresponding adaptive random number MLMC Euler method. A key challenge in the analysis of the algorithm in Theorem 1 is the approximation of probability distributions by means of random bits. A problem very closely related to the quantization problem, i.e., the optimal approximation of a given probability measure (on a separable Hilbert space) by means of a probability measure with finite support size. Though we have shown that the random bit approximation of the standard normal distribution is 'harder' than the corresponding quantization problem (lower weak rate of convergence), we have been able to establish the same weak rate of convergence as for the corresponding quantization problem in the case of the distribution of a Brownian bridge on L2([0,1]), the distribution of the solution of a scalar SDE on L2([0,1]), and the distribution of a centered Gaussian random element in a separable Hilbert space.
Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density e−f(x), given access to the gradient of f. A particular case of interest is that of a d-dimensional Gaussian distribution with covariance matrix Σ, in which case f(x)=x⊤Σ−1x. We show that HMC can sample from a distribution that is ε-close in total variation distance using O(κd1/4log(1/ε)) gradient queries, where κ is the condition number of Σ. Our algorithm uses long and random integration times for the Hamiltonian dynamics. This contrasts with (and was motivated by) recent results that give an Ω(κd1/2) query lower bound for HMC with fixed integration times, even for the Gaussian case.