• search hit 1 of 1059
Back to Result List

## Random Bits for Quadrature of SDEs

• In this thesis we study a variant of the quadrature problem for stochastic differential equations (SDEs), namely the approximation of expectations $$\mathrm{E}(f(X))$$, where $$X = (X(t))_{t \in [0,1]}$$ is the solution of an SDE and $$f \colon C([0,1],\mathbb{R}^r) \to \mathbb{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 \colon \mathbb{R}^r \to \mathbb{R}^r$$ and the diffusion coefficient $$b \colon \mathbb{R}^r \to \mathbb{R}^{r \times 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_\ell = N_\ell(\varepsilon,F) = \begin{cases} \lceil{(L+1) \cdot 2^{-\ell} \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F = F_p,\\ \lceil{(L+1) \cdot 2^{-\ell} \cdot \max(\ell,1) \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F=f_\infty \end{cases}$ for $$\ell = 0,\ldots,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 $$\varepsilon \in {]0,1/2[}$$.  Hence, in terms of the $$\varepsilon$$-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 $$L_2([0,1])$$, the distribution of the solution of a scalar SDE on $$L_2([0,1])$$, and the distribution of a centered Gaussian random element in a separable Hilbert space.
• In der vorliegenden Arbeit studieren wir das Quadraturproblem für stochastische Differentialgleichungen (SDEs). Genauer die Approximation des Erwartungswertes $$\mathrm{E}(f(X))$$, wobei $$X = (X(t))_{t \in [0,1]}$$ die Lösung einer SDE ist und $$f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R}$$ ist eine Funktion, die jede Realisierung von $$X$$ in die reellen Zahlen abbildet. Der entscheidende Unterschied in dieser Arbeit ist die Betrachtung von randomisierten (Monte Carlo) Algorithmen, die lediglich Zugriff auf Random Bits anstelle von Zufallszahlen haben. Das heißt an Stelle von auf $$[0,1]$$ uniform verteilten Zufallsvariablen beschränken wir uns auf auf $$\{0,1\}$$ uniform verteilte Zufallsvariablen. Darüber hinaus nehmen wir an, dass alle weiteren Operationen wie z.B. arithmetische Operationen, Auswertungen elementarer Funktionen und Orakelaufrufe zur Auswertung von $$f$$ im "real number model of computation" betrachtet werden, d.h. sie werden exakt ausgeführt. Im Folgenden geben wir eine detaillierte Beschreibung des Quadraturproblems. Wir sind an der Approximation von \begin{align*} S(f) = \mathrm{E}(f(X)) \end{align*} interessiert, wobei $$X$$ die Lösung einer $$r$$-dimensionalen autonomen SDE der 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*} mit deterministischem Anfangswert \begin{align*} X(0) = x_0 \in \mathbb{R}^r \end{align*} ist. Diese wird getrieben von einer $$d$$-dimensionalen Brownschen Bewegung und wir nehmen an, dass der Driftkoeffizient $$a \colon \mathbb{R}^r \to \mathbb{R}^r$$ und der Diffusionskoeffizient $$b \colon \mathbb{R}^r \to \mathbb{R}^{r \times d}$$ global Lipschitz sind. Für die Funktionenklassen \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*} und \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*} haben wir Folgendes gezeigt.  $$\textit{Theorem 1.}$$ Es existiert ein Random Bit multilevel Monte Carlo (MLMC) Algorithmus $$M$$ mit maximalem Level $L = L(\varepsilon,F) = \begin{cases}\lceil{\log_2(\varepsilon^{-2}}\rceil, &\text{falls} \ F = F_p,\\ \lceil{\log_2(\varepsilon^{-2} + \log_2(\log_2(\varepsilon^{-1}))}\rceil, &\text{falls} \ F = F_\infty \end{cases}$ und Wiederholungszahlen $N_\ell = N_\ell(\varepsilon,F) = \begin{cases} \lceil{(L+1) \cdot 2^{-\ell} \cdot \varepsilon^{-2}}\rceil, & \text{falls} \ F = F_p,\\ \lceil{(L+1) \cdot 2^{-\ell} \cdot \max(\ell,1) \cdot \varepsilon^{-2}}\rceil, & \text{falls} \ F=f_\infty \end{cases}$ für $$\ell = 0,\ldots,L$$, für den es eine positive Konstante $$c$$ gibt, sodass \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*} und \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{falls} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{falls} \ F=F_\infty \end{cases} \end{align*} für jedes $$\varepsilon \in {]0,1/2[}$$.  Im Kontext der $$\varepsilon$$-Komplexität \begin{align*} \mathrm{comp}(\varepsilon,F) = \inf\bigl\{\mathrm{cost}(M,F) \colon M \ \text{ist ein Random Bit MC Algorithmus}, \mathrm{error}(M,F) \leq \varepsilon\bigr\} \end{align*} liefert dies die obere Schranke \begin{align*} \mathrm{comp}(\varepsilon,F) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{falls} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{falls} \ F=F_\infty \end{cases} \end{align*} für eine positive Konstante $$c$$. Folglich haben wir für die $$\varepsilon$$-Komplexität von Random Bit MLMC Euler Algorithmen bezüglich der schwachen Asymptotik dieselbe obere Schranke bewiesen, wie für MLMC Euler Algorithmen mit Zugriff auf uniform auf $$[0,1]$$ verteilte Zufallsvariablen. In diesem Sinn sind Random Bits für unsere Problemstellung genauso mächtig wie Zufallszahlen. Weiter zeigen und diskutieren wir numerische Ergebnisse für einen nicht analysierten adaptiven Random Bit MLMC Euler Algorithmus im Fall von Brownscher Bewegung, geometrischer Brownscher Bewegung, Ornstein-Uhlenbeck SDE und Cox-Ingersoll-Ross SDE. Ein Schlüsselproblem in der Analyse des Algorithmus von Theorem 1 ist die Approximation von Wahrscheinlichkeitsverteilungen basierend auf Random Bits. Dieses Problem ist sehr nah verwandt mit dem Problem der Quantisierung, der optimalen Approximation eines gegebenen Wahrscheinlichkeitsmaßes (auf einem separablen Hilbert Raum) durch ein Wahrscheinlichkeitsmaß mit endlichem Träger. Obwohl wir gezeigt haben, dass die Random Bit Approximation der Standardnormalverteilung schwieriger ist als das zugehörige Quantisierungsproblem (geringere schwache Konvergenzrate), konnten wir zeigen, dass die schwachen Konvergenzraten für die Verteilung einer Brownschen Brücke in $$L_2([0,1])$$, die Verteilung der Lösung einer skalaren SDE in $$L_2([0,1])$$ und der Verteilung eines zentrierten Gauß-Prozesses in einem separablen Hilbertraum übereinstimmen.