Multilevel Picard approximations
for McKean–Vlasov stochastic differential equations
with nonconstant diffusion
February 05, 2025
Abstract
We introduce multilevel Picard (MLP) approximations for McKean–Vlasov stochastic differential equations (SDEs) with nonconstant diffusion coefficient. Under standard Lipschitz assumptions on the coefficients, we show that the MLP algorithm approximates the solution of the SDE in the \(L^2\)-sense without the curse of dimensionality. The latter means that its computational cost grows at most polynomially in both the dimension and the reciprocal of the prescribed error tolerance. In two numerical experiments, we demonstrate its applicability by approximating McKean–Vlasov SDEs in dimensions up to 1000.
1 Introduction↩︎
McKean–Vlasov stochastic differential equations (SDEs) provide a mathematical framework to analyze the limiting behavior of stochastic systems of weakly interacting particles. In order to describe the limit, these SDEs not only depend on the state of the process but also on their distribution, and are therefore also referred to as distribution-dependent SDEs or mean-field SDEs in the literature. First introduced by McKean in [1] to model the Vlasov equation, these equations have since found applications in various fields, including statistical physics (see, e.g., [2]–[5]), mathematical biology (see, e.g., [6]–[10]), social sciences (see, e.g., [11]–[13]), mean-field games (see, e.g., [14]–[16]), stochastic control (see, e.g., [17]), mathematical finance (see, e.g., [18]), and the analysis of neural networks (see, e.g., [19]–[22]).
More precisely, for \(d \in {\mathbb{N}}\) and terminal time \(T > 0\), we consider McKean–Vlasov SDEs defined for every \(t \in [0,T]\) by \[\label{EqMcKV} X^d_\infty(t) = \xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[\mu_d(x,X^d_\infty(s))\right]\!|_{x=X^d_\infty(s)}\,ds + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma_d(x,X^d_\infty(s))\right]\!|_{x=X^d_\infty(s)}\,dW^d(s),\tag{1}\] with initial value \(\xi_d \in {\mathbb{R}}^d\), where \(\mu_d: {\mathbb{R}}^d \times {\mathbb{R}}^d \rightarrow {\mathbb{R}}^d\) and \(\sigma_d: {\mathbb{R}}^d \times {\mathbb{R}}^d \rightarrow {\mathbb{R}}^{d \times d}\) are sufficiently regular functions, and where \(W^d = (W^d(t))_{t \in [0,T]}\) is a \(d\)-dimensional standard Brownian motion. The solution of 1 can be seen as the limit of weakly interacting particles \((\mathcal{X}^{d,n}_N)_{n = 1,...,N}\), as \(N \rightarrow \infty\), where each particle \(\mathcal{X}^{d,n}_N := (\mathcal{X}^{d,n}_N(t))_{t \in [0,T]}\) satisfies the SDE defined for every \(t \in [0,T]\) by \[\mathcal{X}^{d,n}_N(t) = \xi_d + \frac{1}{N} \sum_{m=1}^N \int_0^t \mu_d(\mathcal{X}^{d,n}_N(s),\mathcal{X}^{d,m}_N(s)) ds + \frac{1}{N} \sum_{m=1}^N \int_0^t \sigma_d(\mathcal{X}^{d,n}_N(s),\mathcal{X}^{d,m}_N(s)) dW^{d,n}(s).\] This phenomenon is called the propagation of chaos and was studied in [2], [3], [23]–[25]. While existence and uniqueness of 1 have been established in [3], [26]–[28], the numerical approximation of 1 has been considered in, e.g., [29]–[48].
In this paper, we are interested in the numerical approximation of high-dimensional McKean–Vlasov SDEs. Our contribution is twofold: We introduce a multilevel Picard (MLP) approximation of 1 and show that it overcomes the curse of dimensionality when approximating 1 in the \(L^2\)-sense. The latter means that the computational cost of the MLP algorithm grows at most polynomially in the space dimension \(d\) of the SDE 1 and the reciprocal \(\epsilon^{-1}\) of the prescribed \(L^2\)-error tolerance \(\epsilon\). Second, we demonstrate the practical applicability of the MLP algorithm in two numerical examples by approximating McKean–Vlasov SDEs in dimensions up to 1000.
In the literature, only a few papers discuss the numerical approximation of high-dimensional McKean–Vlasov SDEs. First, [49] has shown that the MLP algorithm does not suffer from the curse of dimensionality when approximating McKean–Vlasov SDEs with constant diffusion coefficient \(\sigma_d\), whence our paper can be seen as an extension to nonconstant diffusions. This is highly relevant for several applications across different fields: McKean–Vlasov SDEs with nonconstant diffusion arise in the stochastic Ginzburg-Landau equation in physics [50], in the Cucker–Smale model in flocking theory [51], as well as in spatially structured neuronal networks, the FitzHugh–Nagumo model, and the Hodgkin–Huxley model in neuronal biology [9], [10], to mention a few. Moreover, [52] introduced an MLP algorithm for approximating ordinary (instead of stochastic) differential equations with expectation, which overcomes the curse of dimensionality.
In recent years, [53]–[56] have adopted deep learning techniques to approximately solve McKean–Vlasov SDEs of the form 1 . While [54] established an a priori error estimate under specific conditions (but not a full convergence and complexity analysis), only [56] proved that rectified deep neural networks do not suffer from the curse of dimensionality. However, the numerical examples presented in [53]–[55] are rather low-dimensional (\(d \leq 15\)), whereas the results in [56] remain purely theoretical without an explicit algorithm to approximate 1 .
The following theorem is the main result of this paper. Hereby, we denote for every \(d\in {\mathbb{N}}\) by \(\lVert\cdot \rVert\colon {\mathbb{R}}^d \to [0,\infty)\) the standard norm on \({\mathbb{R}}^d\), i.e., for all \(x=(x_i)_{i\in [1,d]\cap{\mathbb{Z}}}\in {\mathbb{R}}^d\) we have that \(\lVert x\rVert^2=\sum_{i=1}^{d}\lvert x_i\rvert^2\). For every \(d\in {\mathbb{N}}\) we also denote by \(\lVert\cdot \rVert\colon {\mathbb{R}}^{d\times d} \to [0,\infty)\) the Hilbert-Schmidt norm on \({\mathbb{R}}^{d\times d}\), i.e., for all \(x=(x_{ij})_{i,j\in [1,d]\cap{\mathbb{Z}}}\in {\mathbb{R}}^{d\times d}\) we have that \(\lVert x\rVert^2=\sum_{i,j=1}^{d}\lvert x_{ij}\rvert^2\).
Theorem 1. Let \(T\in (0,\infty)\), \(c\in [1,\infty)\), \(\Theta=\cup_{n\in {\mathbb{N}}}({\mathbb{N}}_0)^n\). For every \(d\in {\mathbb{N}}\) let \(\xi_d\in {\mathbb{R}}^d\), \(\mu_d \in C({\mathbb{R}}^d\times{\mathbb{R}}^d,{\mathbb{R}}^d)\), \(\sigma_d \in C({\mathbb{R}}^d\times{\mathbb{R}}^d,{\mathbb{R}}^{d\times d})\). For every \(K\in {\mathbb{N}}\) let \(\llcorner \cdot\lrcorner _K : [0,T] \rightarrow [0,T]\) satisfy for all \(t\in (0,T]\) that \(\llcorner t\lrcorner _K=\sup( (0,t)\cap\{0,\frac{T}{K},\frac{2T}{K}\ldots,T\})\) and \(\llcorner 0\lrcorner _K=0\). Assume for all \(d\in {\mathbb{N}}\), \(x_1,x_2,y_1,y_2 \in {\mathbb{R}}^d\) that \[\begin{align} \max \left\{ \left\lVert \mu_d(x_1,x_2)-\mu_d(y_1,y_2)\right\rVert , \left\lVert \sigma_d(x_1,x_2)-\sigma_d(y_1,y_2)\right\rVert \right\}\leq 0.5c \lVert x_1-y_1\rVert+0.5c \lVert x_2-y_2\rVert, \label{a11b} \end{align}\tag{2}\] \[\begin{align} \lVert\xi_d\rVert+ \lVert\mu_d (0,0)\rVert+ \lVert \sigma_d(0,0) \rVert\leq cd^c.\label{a11c} \end{align}\tag{3}\] Let \((\Omega,\mathcal{F},{\mathbb{P}}, ({\mathbb{F}}_t)_{t\in [0,T]})\) be a filtered probability space which satisfies the usual conditions1. Let \(\mathfrak{u}^\theta\colon \Omega\to [0,1]\), \(\theta\in \Theta\), be independent and identically distributed random variables satisfying for all \(\theta\in \Theta\), \(t\in [0,1]\) that \({\mathbb{P}}(\mathfrak{u}^{\theta}\leq t)=t\). For every \(d\in {\mathbb{N}}\) let \(W^{d,\theta}=(W^{d,\theta}(t))_{t\in [0,T]}\colon [0,T]\times \Omega\to {\mathbb{R}}^d\), \(\theta\in \Theta\), be independent standard \(({\mathbb{F}}_t)_{t\in [0,T]}\)-Brownian motions. Assume that \((\mathfrak{u}^\theta)_{\theta\in \Theta}\) and \((W^{d,\theta})_{d\in {\mathbb{N}},\theta\in \Theta}\) are independent. Let \(X_{n,m,K}^{d,\theta}\colon [0,T]\times \Omega\to {\mathbb{R}}^d\), \(\theta\in \Theta\), \(d,m,K\in {\mathbb{N}}\), \(n\in {\mathbb{N}}_0\), satisfy for all \(\theta\in \Theta\), \(d,K,m,n\in {\mathbb{N}}\), \(t\in [0,T]\) that \(X^{d,\theta}_{0,m,K}(t)=0\) and \[\begin{align} \begin{aligned} & X^{d,\theta}_{n,m,K}(t)= \xi_d +t\mu_d(0,0)+\sigma_d(0,0)W^{d,\theta}(t)\\ &+ \sum_{\ell=1}^{n-1}\sum_{k=1}^{m^{n-\ell}} \frac{t}{m^{n-\ell}} \Bigl[ \mu_d (X_{\ell,m,K}^{d,\theta} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K ),X_{\ell,m,K}^{d,(\theta,n,k,\ell)} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K ))\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,\theta} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K ),X_{\ell-1,m,K}^{d,(\theta,n,k,\ell)} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K )) \Bigr] \\ &+ \sum_{\ell=1}^{n-1}\sum_{k=1}^{m^{n-\ell}}\int_{0}^{t} \frac{1}{m^{n-\ell}} \Bigl[ \sigma_d(X_{\ell,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K ))\\ &\qquad\qquad\qquad\qquad\qquad - \sigma_d(X_{\ell-1,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K ))\Bigr] dW^{d,\theta}(s). \end{aligned}\label{a05c} \end{align}\tag{4}\] For every \(d\in {\mathbb{N}}\) let \(\mathsf{cost}_{\mu_d}\) and \(\mathsf{cost}_{\sigma_d}\) be an upper bound of the computational cost to calculate \(\mu_d (x,y)\) and \(\sigma_d(x,y)\) for any \(x,y\in {\mathbb{R}}^d\). Let \(\mathsf{cost}_\mathsf{rv}\) be an upper bound of the computational cost to generate a scalar random variable. For every \(d,m,K\in {\mathbb{N}}\), \(n\in {\mathbb{N}}_0\) let \(\mathsf{C}_{n,m,K}^d\) denote the computational cost to construct the whole discrete process \((X_{n,m,K}^{d,\theta}(\frac{kT}{K}))_{k\in [1,K]\cap{\mathbb{Z}}}\) given that we have prepared a discrete Brownian path \(W^{d,\theta}(\frac{kT}{K}))_{k\in [1,K]\cap{\mathbb{Z}}}\). Assume for all \(d\in {\mathbb{N}}\) that \[\begin{align} \mathsf{cost}_{\mu_d} + \mathsf{cost}_{\sigma_d}+\mathsf{cost}_\mathsf{rv}\leq cd^c.\label{c10} \end{align}\tag{5}\] Then the following holds:
(i) For all \(d\in {\mathbb{N}}\), \(\theta\in \Theta\) there exists a unique \({\mathbb{R}}^d\)-valued \(({\mathbb{F}}_t)_{t\in [0,T]}\)-adapted process \(X_\infty^{d,\theta}=(X_\infty^{d,\theta}(t))_{t\in [0,T]}\) with continuous sample paths such that we have \({\mathbb{P}}\)-a.s.for all \(t\in [0,T]\) that \(\sup_{s\in [0,T]}\lVert X_\infty^{d,\theta}(s)\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}<\infty\) and \[\begin{align} \label{b02c} X_\infty^{d,\theta}(t) =\xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[\mu_d(x,X_\infty^{d,\theta}(s))\right]\!|_{x=X_\infty^{d,\theta}(s)}\,ds + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma_d(x,X_\infty^{d,\theta}(s))\right]\!|_{x=X_\infty^{d,\theta}(s)}\,dW^{d,\theta}(s). \end{align}\tag{6}\]
(ii) There exist \((\mathfrak{C}_\delta)_{\delta\in (0,1)}\subseteq {\mathbb{R}}\), \((\mathsf{n}_{d,\epsilon})_{d\in {\mathbb{N}},\epsilon\in (0,1)}\subseteq {\mathbb{N}}\) such that for all \(d\in {\mathbb{N}}\), \(\delta,\epsilon\in (0,1)\) we have that \[\begin{align} \label{c19c} \sup_{k\in [\mathsf{n}_{d,\epsilon},\infty)\cap{\mathbb{Z}}} \sup _{t\in [0,T]} \left\lVert X^{d,0}_{k,k,k^k}(t)-X^{d,0}_\infty(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}<\epsilon \end{align}\tag{7}\] and \[\begin{align} \label{c19d} \mathsf{C}_{\mathsf{n}_{d,\epsilon},\mathsf{n}_{d,\epsilon}, (\mathsf{n}_{d,\epsilon})^{\mathsf{n}_{d,\epsilon}}}^d<(d^{c+1})^6\mathfrak{C}_\delta\epsilon^{-(4+\delta)}. \end{align}\tag{8}\]
Remark 1. Note that the McKean–Vlasov SDEs 6 can be equivalently written using the laws of \((X_\infty^{d,\theta}(s))_{s \in [0,T]}\), instead of the expectation. More precisely, for every fixed \(d \in {\mathbb{N}}\), we denote by \(P_2({\mathbb{R}}^d)\) the set of probability measures \(\nu\) on \({\mathbb{R}}^d\) satisfying \(\int_{{\mathbb{R}}^d} x^2 \nu(dx) < \infty\) and define the functions \({\mathbb{R}}^d \times P_2({\mathbb{R}}^d) \ni (x,\nu) \mapsto \widetilde{\mu}_d(x,\nu) := \int_{{\mathbb{R}}^d} \mu_d(x,y) \nu(dy) \in {\mathbb{R}}^d\) and \({\mathbb{R}}^d \times P_2({\mathbb{R}}^d) \ni (x,\nu) \mapsto \widetilde{\sigma}_d(x,\nu) := \int_{{\mathbb{R}}^d} \sigma_d(x,y) \nu(dy) \in {\mathbb{R}}^{d \times d}\). Then, it holds \({\mathbb{P}}\)-a.s.for all \(\theta \in \Theta\), \(t\in [0,T]\) that \[\begin{align} X_\infty^{d,\theta}(t)&=\xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[\mu_d(x,X_\infty^{d,\theta}(s))\right]\!|_{x=X_\infty^{d,\theta}(s)}\,ds + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma_d(x,X_\infty^{d,\theta}(s))\right]\!|_{x=X_\infty^{d,\theta}(s)}\,dW^{d,\theta}(s) \\ &=\xi_d+\int_{0}^{t} \widetilde{\mu}_d(X_\infty^{d,\theta}(s),\nu_{X_\infty^{d,\theta}(s)}) ds + \int_{0}^{t} \widetilde{\sigma}_d(X_\infty^{d,\theta}(s),\nu_{X_\infty^{d,\theta}(s)})\,dW^{d,\theta}(s), \end{align}\] where \(\nu_{X_\infty^{d,\theta}(s)} \in P_2({\mathbb{R}}^d)\) denotes the law of the random variable \(X_\infty^{d,\theta}(s)\), which is defined as \(\nu_{X_\infty^{d,\theta}(s)}[A] := {\mathbb{P}}[X_\infty^{d,\theta}(s) \in A]\) for all Borel-subsets \(A \subseteq {\mathbb{R}}^d\).
Remark 2. Under the assumptions of Theorem 1, for all \(\theta\in \Theta\), \(d,K,m,n\in {\mathbb{N}}\), \(\ell\in[1,n-1]\cap{\mathbb{Z}}\), \(k\in [1,m^{n-\ell}]\cap{\mathbb{Z}}\), \(t\in [0,T]\), \(J\in [0,K-1]\cap{\mathbb{Z}}\) with \(t=\frac{JT}{K}\) we have that \[\begin{align} & \int_{0}^{t}\left[\sigma_d(X_{\ell,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K )) -\sigma_d(X_{\ell-1,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K ) \right] dW^{d,\theta}(s)\nonumber\\ &= \sum_{j=0}^{J-1}\left[ \sigma_d(X_{\ell,m,K}^{d,\theta} (\tfrac{jT}{K} ),X_{\ell,m,K}^{d,(\theta,n,k,\ell)} (\tfrac{jT}{K})) - \sigma_d(X_{\ell-1,m,K}^{d,\theta} (\tfrac{jT}{K} ),X_{\ell-1,m,K}^{d,(\theta,n,k,\ell)} (\tfrac{jT}{K}))\right] (W^{d,\theta}(\tfrac{(j+1)T}{K})-W^{d,\theta}(\tfrac{jT}{K}) ). \end{align}\] Thus, we see that the stochastic integral in 4 is time-discretized and hence implementable.
Theorem 1 proves mathematically that the multilevel Picard (MLP) approximation 4 overcomes the curse of dimensionality when approximating the McKean–Vlasov SDE 6 . Indeed, by 7 and 8 , the computational cost \(\mathsf{C}_{n,m,K}^d\) of the MLP algorithm grows at most polynomially in both the state-space dimension \(d\) and the reciprocal \(\epsilon^{-1}\) of the prescribed \(L^2\)-error tolerance \(\epsilon\).
Let us give some motivations for the numerical schema 4 . First, we start with an iteration defined as follows \(X^d_{0}(t)=0\) and \[\begin{align} X^d_n(t) &= \xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[ \mu_d(x,X^d_{n-1}(s))\right]\!|_{x=X^d_{n-1}(s)}\,ds + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma_d(x,X^d_{n-1}(s))\right]\!|_{x=X^d_{n-1}(s)}\,dW^d(s) \end{align}\] for \(n\in {\mathbb{N}}\). Note that the r.h.s. can be written as a telescoping sum: \[\begin{align} X^d_n(t) &= \xi_d+t\mu_d(0,0)+\sigma_d(0,0)W^{d,\theta}(t)\nonumber\\&\quad +\int_{0}^{t}\sum_{\ell=1}^{n-1}{\mathbb{E}}\!\left[ \mu_d(x,X^d_{\ell}(s))\right]\!|_{x=X^d_{\ell}(s)}- {\mathbb{E}}\!\left[ \mu_d(x,X^d_{\ell-1}(s))\right]\!|_{x=X^d_{\ell-1}(s)} \,ds\nonumber\\ &\quad + \int_{0}^{t}\sum_{\ell=1}^{n-1}{\mathbb{E}}\!\left[\sigma_d(x,X^d_{\ell}(s))\right]\!|_{x=X^d_{\ell}(s)} -{\mathbb{E}}\!\left[\sigma_d(x,X^d_{\ell-1}(s))\right]\!|_{x=X^d_{\ell-1}(s)} \,dW^d(s) \end{align}\] where the index \(\ell\) can be interpreted as the corresponding level. By replacing here all expectations and integrals by corresponding Monte-Carlo approximations we derive our multilevel Picard approximation scheme 4 . More precisely, the ideas can be describe as follows. First, we approximate an integral \(\int_0^t h(s)\,ds\) for a random function \(h\) by \(th(\mathfrak{u})\) where \(\mathfrak{u}\) is uniformly distributed on \([0,1]\) and independent of \(h\). In order to approximate the expectations \({\mathbb{E}}\!\left[ \mu_d(x,X^d_{\ell-1}(s))\right]\!|_{x=X^d_{\ell-1}(s)}\) and \({\mathbb{E}}\!\left[ \sigma_d(x,X^d_{\ell-1}(s))\right]\!|_{x=X^d_{\ell-1}(s)}\) we take one sample \(X^{d,\theta}_{\ell,m,K}\), which is also generated by the Brownian motion \(W^{d,\theta}\), and \(m^{n-\ell}\) independent samples \(X^{d,(\theta,n,k,\ell)}\), \(k\in \{1,2,\ldots,m^{n-\ell}\}\), which are respectively generated by the independent Brownian motions \(W^{d,(\theta,n,k,\ell)}\), \(k\in \{1,2,\ldots,m^{n-\ell}\}\). The main novelty of the numerical scheme in 4 in Theorem 1 compared to [49] lies in storing the entire process \((X_{n,m,K}^{d,\theta}(t))_{t\in [0,T]}\) rather than only one random variable \(X_{n,m,K}^{d,\theta}(t)\). Indeed, by retaining the whole path \((X_{n,m,K}^{d,\theta}(t))_{t\in [0,T]}\), we can approximate the stochastic integral arising in McKean–Vlasov SDEs with nonconstant diffusion coefficient, which was not necessary for the constant diffusion case in [49] where the stochastic integral is just a normally distributed random variable. Since we cannot save a process \(Y\) at all time points \(t\in [0,T]\) we only save the discrete trajectory \((Y(\llcorner t\lrcorner _K))_{t\in [0,T]}\). Here and in 4 the index \(K\) denote the number of steps of the time discretization to approximate the stochastic integrals. While this approach may seem inefficient at first sight, our numerical experiments demonstrate its effectiveness even in high dimensions. Moreover, for many applications of McKean–Vlasov SDEs, one requires the computation of the entire solution trajectory \((X^{d,\theta}_{\infty}(t))_{t\in [0,T]}\) instead of one single space-time point \(X^{d,\theta}_{\infty}(t)\), which our method can do.
Remark 3. In Theorem 1, the higher complexity of order \(\epsilon^{-(4+\delta)}\) compared to \(\epsilon^{-(2+\delta)}\) in the case when \(\sigma\) is constant is due to the fact that we have to approximate the stochastic integrals and therefore need to save the whole trajectory of the approximation solution. As seen in 26 , the \(L^2\) error consists of two parts: an MLP error (the first term) and a discretization error (the second term). These two errors should be balanced. This leads to the choice \(m=n\) and \(K=n^n\). As a result, we obtain a computational complexity of order \(\epsilon^{-(4+\delta)}\). We believe that this computational complexity is not sharp. As a future research we would like to design an algorithm which can overcome the curse of dimensionality with computational complexity of order \(\epsilon^{-(2+\delta)}\), the same computational complexity as in the case \(\sigma\) is constant.
Remark 4. In Theorem 1 the \(dt\)-integral can also be approximated by time discretization instead of uniform Monte-Carlo sampling. It can be seen by slightly adapting the proof that the computational complexity is still of order \(\epsilon^{-(4+\delta)}\). However, in practice, the algorithm runs faster when we use uniform Monte-Carlo sampling because it does not need to evaluate \(\mu_d\) along the whole discrete trajectory but only one random point on it. In the time integral we need to introduce the rounding because we cannot save the whole trajectory of the approximation solution \((X_{n,m,K}(t))_{t\in [0,T]}\) but only its discrete part \((X_{n,m,K}(kT/K))_{k\in [0,K]\cap\mathbb{Z}}\).
Remark 5. Note that the MLP scheme 4 outputs only a single trajectory approximating the solution to the McKean-Vlasov SDE 6 . However, the lower levels \(X_{\ell,m,K}^{d,(\theta,n,k,\ell)}\), \(k \in \lbrace 1,...,m^{n-\ell} \rbrace\) and \(\ell \in \lbrace 1,...,n-1 \rbrace\), of the MLP algorithm can be used to approximate additional statistical quantities. For example, we use the lower levels in the numerical example of Section 2.2 to approximate the expectation in the drift coefficient of the McKean-Vlasov SDE 6 .
The remainder of this article is organized as follows. In Section 2, we provide two numerical examples to approximate the solution of 1 in dimension up to 1000, followed by the conclusion in Section 3. In Section 4, we show an auxiliary result on Picard iterations of the McKean–Vlasov SDE 1 , while Section 5 contains the proof of the main result in Theorem 1.
2 Numerical experiments↩︎
In this section, we provide two numerical examples2 to illustrate how the solution of the McKean-Vlasov SDE 1 can be approximated by the multilevel Picard (MLP) scheme 4 . First, let us summarize the MLP scheme 4 as pseudocode in Algorithm 1.
2.1 Mean-field Ornstein-Uhlenbeck model↩︎
In the first example, we consider an Ornstein-Uhlenbeck process with a mean-field term in the drift and diffusion coefficient (see [57]). More precisely, we assume that the \((\mathbb{F}_t)_{t \in [0,T]}\)-adapted process \(X^{d,\theta}_\infty = (X^{d,\theta}_\infty(t))_{t \in [0,T]}\) for every \(t \in [0,T]\) is given by \[\label{EqDefMfOU} \begin{align} X^{d,\theta}_\infty(t) & = \xi_d + \int_0^t \left( a_0 + A_1 X^{d,\theta}_\infty(s) + A_2 {\mathbb{E}}\!\left[ X^{d,\theta}_\infty(s) \right] \right) ds + \sum_{k=1}^d \int_0^t \left( b_k + B_k {\mathbb{E}}\!\left[ X^{d,\theta}_\infty(s) \right] \right) dW^{d,\theta,k}(s), \end{align}\tag{9}\] where \(\xi_d \in {\mathbb{R}}^d\) is the initial value, where \(a_0,b_1,...,b_d \in {\mathbb{R}}^d\) are vectors, and where \(A_1, A_2, B_1,...,B_d \in {\mathbb{R}}^{d \times d}\) are matrices. Comparing to Theorem 1, this corresponds to the drift \(\mu_d(x_1,x_2) = a_0 + A_1 x_1 + A_2 x_2\) and diffusion coefficient \(\sigma_d(x_1,x_2) = (b_k+B_k x_2)_{k=1,...,d}\) satisfying 2 and 3 . Moreover, by taking the expectation in 9 and using Fubini’s theorem, we have \[{\mathbb{E}}\!\left[ X^{d,\theta}_\infty(t) \right] = \xi_d + a_0 t + (A_1 + A_2) \int_0^t {\mathbb{E}}\!\left[ X^{d,\theta}_\infty(s) \right] ds,\] whose solution is given by \[\label{EqMeanMfOU} m_d(t) := {\mathbb{E}}\!\left[ X^{d,\theta}_\infty(t) \right] = e^{(A_1+A_2)t} \xi_d + \int_0^t e^{(A_1+A_2)(t-s)} a_0 ds.\tag{10}\] For different dimensions \(d \in \lbrace 10, 50, 100, 500, 1000 \rbrace\) and levels \(n = m \in \lbrace 1,...,5 \rbrace\) with \(K = m^n\), we run the algorithm \(10\) times with terminal time \(T = 1\), initial value \(\xi_d = (20,...,20)^\top\), and randomly initialized parameters that are fixed over the different levels and runs, i.e., \[\begin{align} a & \sim \mathcal{N}_d\big( 0,(20\sqrt{d})^{-1} I_d \big), & & & \operatorname{vec}(A_k) & \sim \mathcal{N}_{d^2}\big( 0,(100d)^{-1} I_{d^2} \big) & & k \in \lbrace 1,2 \rbrace \\ b_k & \sim \mathcal{N}_d\big( 0,(5d)^{-1} I_d \big), & & k \in \lbrace 1,...,d \rbrace, \quad & \operatorname{vec}(B_k) & \sim \mathcal{N}_{d^2}\big( 0,(5d)^{-1} I_{d^2} \big) & & k \in \lbrace 1,...,d \rbrace, \end{align}\] which are all independent of each other, where \(\operatorname{vec}(A) := (a_{1,1},a_{1,2},...,a_{d,d})^\top \in {\mathbb{R}}^{d^2}\) for \(A := (a_{i,j})_{i=1,...,d}^{j=1,...,d}\), where \(\mathcal{N}_d(0,\Sigma)\) denotes the normal distribution with zero mean and covariance matrix \(\Sigma \in {\mathbb{R}}^{d \times d}\), and where \(I_d \in {\mathbb{R}}^{d \times d}\) is the identity matrix. The results are reported in Table 1 with (\(d^{-1/2}\)-adjusted) \(L^2\)-error given by \[\label{EqDefL2Err} \left( \frac{1}{10 d K} \sum_{r=1}^{10} \sum_{k=1}^K \left\Vert X^{d,\theta}_\infty(\omega_r)(t_k) - X^{d,\theta}_{n,m,K}(\omega_r)(t_k) \right\Vert^2 \right)^\frac{1}{2}.\tag{11}\] Here, the true solution \(X^{d,\theta}_\infty\) is approximated by an Euler-Maruyama scheme of 9 over a finer equidistant time grid \((j T/K_1)_{j=0,...,K_1}\) with \(K_1 := K \lfloor\frac{500}{K} \rfloor + 1\) points. The realizations of the Brownian increments \(\big(\Delta W^{d,\theta,k}(j T/K_1)\big)_{j=0,\dots,K_1}\) on this finer Euler-Maruyama grid are then summed over each time subinterval of the coarser MLP grid to obtain the Brownian increments \(\big(\Delta W^{d,\theta,k}(j T/K)\big)_{j=0,\dots,K}\) used in the MLP approximation.
| Level \(n\), samples per level \(m\), and time points \(K = m^n\) | ||||||
| \(d\) | \(n = m = 1\) | \(n = m = 2\) | \(n = m = 3\) | \(n = m = 4\) | \(n = m = 5\) | |
2.2 Multidimensional geometric Kuramoto model↩︎
In the second example, we consider a multidimensional geometric version of the Kuramoto model, whose original model has been studied in [46], [58]–[60] and the references therein. More precisely, we assume that the \((\mathbb{F}_t)_{t \in [0,T]}\)-adapted process \(X^{d,\theta}_\infty = (X^{d,\theta}_\infty(t))_{t \in [0,T]}\) for every \(t \in [0,T]\) is given by \[\label{EqDefKuramoto} X^{d,\theta}_\infty(t) = \xi_d + \mu_0 \int_0^t {\mathbb{E}}\!\left[ \sin_d\left( x - X^{d,\theta}_\infty(s) \right) \right]\!|_{x = X^{d,\theta}_\infty(s)} ds + \sum_{k=1}^d \int_0^t \Sigma_k X^{d,\theta}_\infty(s) dW^{d,\theta,k}(s),\tag{12}\] where \(\xi_d \in {\mathbb{R}}^d\) is the initial value, where \(\mu_0 \in {\mathbb{R}}\) and \(\Sigma_1,...,\Sigma_d \in {\mathbb{R}}^{d \times d}\) are some parameters, and where \({\mathbb{R}}^d \ni x = (x_1,...,x_d)^\top \mapsto \sin_d(x) := (\sin(x_1),...,\sin(x_d))^\top \in {\mathbb{R}}^d\) denotes the componentwise sine function. Comparing to Theorem 1, this corresponds to the drift \(\mu_d(x_1,x_2) = \mu_0 \sin_d(x_1-x_2)\) and diffusion coefficient \(\sigma_d(x_1,x_2) = (\Sigma_k x_1)_{k=1,...,d}\) satisfying 2 and 3 . Moreover, we have \[\label{EqExpKuramoto} {\mathbb{E}}\!\left[ \sin_d\!\left( x \!-\! X^{d,\theta}_\infty(s) \right) \right] \!|_{x = X^{d,\theta}_\infty(s)} = \sin_d\!\left( X^{d,\theta}_\infty(s) \right) {\mathbb{E}}\!\left[ \cos_d\!\left( X^{d,\theta}_\infty(s) \right) \right] - \cos_d\!\left( X^{d,\theta}_\infty(s) \right) {\mathbb{E}}\!\left[ \sin_d\!\left( X^{d,\theta}_\infty(s) \right) \right].\tag{13}\] For different dimensions \(d \in \lbrace 10, 50, 100, 500, 1000 \rbrace\) and levels \(n = m \in \lbrace 1,...,5 \rbrace\) with \(K = m^n\), we run the algorithm \(10\) times with terminal time \(T = 1\), initial value \(\xi_d = (\xi_d^1,...,\xi_d^d)^\top = (10,...,10)^\top\), parameter \(\mu_0 = 1\), and randomly initialized parameters \((\Sigma_k)_{k=1,...,d}\) that are fixed over the different levels and runs, i.e., samples from the independent random variables \[\begin{align} \operatorname{vec}(\Sigma_k) \sim \mathcal{N}_{d^2}\big( 0, (10d)^{-1} I_{d^2} \big), \qquad k \in \lbrace 1,...,d \rbrace. \end{align}\] The results are reported in Table 2, where the true solution \(X^{d,\theta}_\infty = (X^{d,\theta}_\infty(t))_{t \in [0,T]}^\top\) is approximated by an Euler-Maruyama scheme of 12 over a finer equidistant time grid \((j T/K_1)_{j=0,...,K_1}\) with \(K_1 := K \lfloor \frac{500}{K} \rfloor + 1\) points. For the drift term of 12 , the expectation 13 is approximated by an average over the lower levels of the MLP algorithm, which are then extended from \((j T/K)_{j=0,...,K}\) to \((j T/K)_{j=0,...,K_1}\) by piecewise constant interpolation. Again, the realizations of the Brownian increments \(\big(\Delta W^{d,\theta,k}(j T/K_1)\big)_{j=0,\dots,K_1}\) on the finer Euler-Maruyama grid are then summed over each time subinterval of the coarser MLP grid to obtain the Brownian increments \(\big(\Delta W^{d,\theta,k}(j T/K)\big)_{j=0,\dots,K}\) used in the MLP approximation.
| Level \(n\), samples per level \(m\), and time points \(K = m^n\) | ||||||
| \(d\) | \(n = m = 1\) | \(n = m = 2\) | \(n = m = 3\) | \(n = m = 4\) | \(n = m = 5\) | |
3 Conclusion↩︎
Theorem 1 proves mathematically that the multilevel Picard (MLP) approximation in 4 overcomes the curse of dimensionality when approximating the McKean–Vlasov stochastic differential equation (SDE) in 1 . This means that the computational cost of the MLP algorithm grows at most polynomially in both the state-space dimension \(d\) and the reciprocal \(\epsilon^{-1}\) of the prescribed \(L^2\)-error tolerance \(\epsilon\). Moreover, the two numerical examples demonstrate the practical applicability of the MLP algorithm for the approximation of high-dimensional McKean–Vlasov SDEs. In particular, Table 1 and Table 2 confirm empirically that the MLP approximation overcomes the curse of dimensionality as the (\(d^{-1/2}\)-adjusted) \(L^2\)-error defined in 11 does not increase significantly in the dimension \(d\), while the computational cost seem to increase linearly in \(d\).
4 An auxiliary lemma↩︎
In this section, we show an auxiliary result for solutions to McKean–Vlasov SDEs of the form 1 and its discretization which will be useful for the proof of Theorem 1.
Lemma 6. Let \(T\in (0,\infty)\), \(c\in [1,\infty)\), \(d\in{\mathbb{N}}\), \(\xi_d\in {\mathbb{R}}^d\), \(\mu \in C({\mathbb{R}}^d\times {\mathbb{R}}^d,{\mathbb{R}}^d)\), \(\sigma\in C({\mathbb{R}}^d\times {\mathbb{R}}^d,{\mathbb{R}}^{d\times d})\) satisfy for all \(x_1,x_2,y_1,y_2\in {\mathbb{R}}^d\) that \[\begin{align} \max \left\{ \left\lVert \mu(x_1,x_2)-\mu(y_1,y_2)\right\rVert , \left\lVert \sigma(x_1,x_2)-\sigma(y_1,y_2)\right\rVert \right\}\leq 0.5c \lVert x_1-y_1\rVert+0.5c \lVert x_2-y_2\rVert. \label{a11} \end{align}\tag{14}\] For every \(K\in {\mathbb{N}}\) let \(\llcorner \cdot\lrcorner _K : [0,T] \rightarrow [0,T]\) satisfy for all \(t\in (0,T]\) that \(\llcorner t\lrcorner _K=\sup( (0,t)\cap\{0,\frac{T}{K},\frac{2T}{K}\ldots,T\})\) and \(\llcorner 0\lrcorner _K=0\). For convenience we write for every \(t\in [0,T]\) that \(\llcorner t\lrcorner _\infty=t\). Let \((\Omega,\mathcal{F}, {\mathbb{P}}, ({\mathbb{F}}_t)_{t\in [0,T]})\) be a filtered probability space which satisfies the usual conditions. Let \(W=(W(t))_{t\in [0,T]}\colon [0,T]\times\Omega\to {\mathbb{R}}^d\) be a standard \(({\mathbb{F}}_t)_{t\in [0,T]}\)-Brownian motion. Then the following holds:
(i) For all \(K\in {\mathbb{N}}\cup\{\infty\}\) there exists a unique \(({\mathbb{F}}_t)_{t\in [0,T]}\)-adapted process \(X_K=(X_K(t))_{t\in [0,T]}\) with continuous sample paths such that we have \({\mathbb{P}}\)-a.s.for all \(t\in [0,T]\) that \(\sup_{s\in [0,T]}\lVert X_K(s)\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)}<\infty\) and \[\begin{align} X_K(t)&=\xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[\mu(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\,ds \, + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\,dW(s). \end{align}\]
(ii) For all \(t\in [0,T]\), \(K\in {\mathbb{N}}\cup\{\infty\}\) we have that \[\begin{align} \left\lVert X_K(t)\right\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)} \leq \sqrt{2}\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2t}. \end{align}\]
(iii) For all \(t_1,t_2\in [0,T]\) with \(t_1<t_2\) we have that \[\begin{align} & \left\lVert X_\infty(t_1) -X_\infty(t_2) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\&\leq \sqrt{t_2-t_1}\max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{3(\sqrt{T}+1)^2(T+1)c^2}. \end{align}\]
(iv) For all \(K\in {\mathbb{N}}\), \(t\in [0,T]\) we have that \[\begin{align} & \lVert X_K(t)-X_\infty(t)\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \nonumber\\&\leq 4.5 \sqrt{T/K} \max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\}e^{5(\sqrt{T}+1)^2(T+1)c^2}. \end{align}\]
Proof of 6. Recursion along the time grid shows [a04] for \(K\in {\mathbb{N}}\). Next, let \(\mathcal{P}_2({\mathbb{R}}^d)\) denote the set of probability measure on \({\mathbb{R}}^d\) with finite second moments. Let \(\widetilde{\mu}\colon {\mathbb{R}}^d\times\mathcal{P}_2({\mathbb{R}}^d)\to {\mathbb{R}}^d\), \(\widetilde{\sigma}\colon {\mathbb{R}}^d\times\mathcal{P}_2({\mathbb{R}}^d)\to {\mathbb{R}}^{d\times d}\) satisfy for all \(x\in {\mathbb{R}}^d\), \(\nu\in \mathcal{P}({\mathbb{R}}^d)\) that \(\widetilde{\mu}(x,\nu)= \int_{{\mathbb{R}}^d}\mu (x,y)\,\nu(dy)\), \(\widetilde{\sigma}(x,\nu)= \int_{{\mathbb{R}}^d}\sigma (x,y)\,\nu(dy)\). Following the arguments in the proof of [56] we see that the assumptions of [61] (with \(b\curvearrowleft\widetilde{\mu}\), \(\sigma\curvearrowleft\widetilde{\sigma}\)) are satisfied. Therefore, [61] and Remark 1 show [a04] for \(K=\infty\).
Next, [a04], the triangle inequality, and Itô’s isometry show for all \(t\in[0,T]\), \(K\in {\mathbb{N}}\cup\{\infty\}\) that \[\begin{align} & \left\lVert X_K(t)\right\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)}\nonumber\\ &\leq \lVert\xi_d\rVert+\int_{0}^{t} \left\lVert{\mathbb{E}}\!\left[\mu(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}ds\nonumber\\ &\quad +\left\lVert \int_{0}^{t}{\mathbb{E}}\!\left[\sigma(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\,dW(s)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber \\ &\leq \lVert\xi_d\rVert+ \sqrt{T} \left(\int_{0}^{t} \left\lVert{\mathbb{E}}\!\left[\mu(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\right\rVert^2_{L^2({\mathbb{P}};{\mathbb{R}}^d)}ds\right)^\frac{1}{2}\nonumber\\ &\quad +\left( \int_{0}^{t} \left\lVert {\mathbb{E}}\!\left[\sigma(x,X_K(\llcorner s\lrcorner _K))\right]\!|_{x=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 ds\right)^\frac{1}{2} \nonumber\\ &\leq \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} +(\sqrt{T}+1)c \left(\int_{0}^{t} \lVert X_K(\llcorner s\lrcorner _K)\rVert^2_{L^2({\mathbb{P}};{\mathbb{R}}^d)}ds \right)^\frac{1}{2}. \end{align}\] This and Grönwall’s lemma (cf., e.g., [62]) show for all \(t\in [0,T]\), \(K\in {\mathbb{N}}\cup\{\infty\}\) that \[\begin{align} \left\lVert X_K(t)\right\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)} \leq \sqrt{2}\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2t}. \end{align}\] This proves [a09].
Next, [a09], the fact that \(c\geq 1\), the fact that \(1+\sqrt{2}\leq 3\) show for all \(s\in [0,T]\) that \[\begin{align} &\max\{ \lVert {\mathbb{E}}[\mu(x,X_\infty(s))]|_{x=X_\infty(s)}\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)} ,\lVert{\mathbb{E}}[\sigma(x,X_\infty(s))]|_{x=X_\infty(s)} \rVert_{L^2({\mathbb{P}},{\mathbb{R}}^{d\times d})} \}\nonumber\\ &\leq \max \{\lVert \mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\}+ c \lVert X_\infty(s)\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \max \{\lVert \mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\}\nonumber\\&\quad +c \sqrt{2}\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2T} \nonumber\\ &\leq 3c\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2T}. \end{align}\] This, [a04], the triangle inequality, Jensen’s inequality, Itô’s isometry, and the fact that \(c\geq 1\) show that for all \(t_1,t_2\in [0,T]\) with \(t_1<t_2\) we have that \[\begin{align} & \left\lVert X_\infty(t_1) -X_\infty(t_2) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber \\ &\leq \left\lVert\int_{t_1}^{t_2} {\mathbb{E}}\!\left[ \mu(x,X_\infty(s))\right]|_{x=X_\infty(s)}\,ds\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} + \left\lVert \int_{t_1}^{t_2} {\mathbb{E}}\!\left[ \sigma(x,X_\infty(s))]|_{x=X_\infty(s)}\right]dW(s) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \sqrt{T}\left( \int_{t_1}^{t_2} \left\lVert {\mathbb{E}}\!\left[ \mu(x,X_\infty(s))\right]|_{x=X_\infty(s)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds\right)^\frac{1}{2}\nonumber \\&\quad + \left( \int_{t_1}^{t_2} \left\lVert {\mathbb{E}}\!\left[ \sigma(x,X_\infty(s))]|_{x=X_\infty(s)}\right]\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds\right)^\frac{1}{2}\nonumber\\ &\leq (\sqrt{T}+1)\sqrt{t_2-t_1}3c\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2T}\nonumber\\ &\leq \sqrt{t_2-t_1} \left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu(0,0)\rVert,\lVert\sigma(0,0)\rVert\} \right)3e^{(\sqrt{T}+1)^2c^2(T+1)} \nonumber\\ &\leq \sqrt{t_2-t_1}2(\sqrt{T}+1)\max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{(\sqrt{T}+1)^2(T+1)c^2}\nonumber\\ &\leq \sqrt{t_2-t_1}\max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{3(\sqrt{T}+1)^2(T+1)c^2}.\label{c05} \end{align}\tag{15}\] This shows [c02].
Next, 14 and the triangle inequality prove for all \(s\in[0,T]\), \(K\in {\mathbb{N}}\) that \[\begin{align} & \left\lVert {\mathbb{E}}[\mu(x,X_\infty(s))]|_{x=X_\infty(s)} - {\mathbb{E}}[\mu(y,X_K(\llcorner s\lrcorner _K))]|_{y=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber \\ & \leq \left\lVert \left\lVert \mu(x,X_\infty(s))-\mu(y,X_K(\llcorner s\lrcorner _K)) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}|_{(x,y)=((X_\infty(s)),X_K(\llcorner s\lrcorner _K))}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber\\ & \leq \left\lVert \left[0.5c \lVert x-y\rVert+ 0.5c\left\lVert X_\infty(s))-X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \right]\!|_{(x,y)=((X_\infty(s)),X_K(\llcorner s\lrcorner _K))}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber\\ &\leq c \left\lVert X_\infty(s)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq c\left\lVert X_\infty(s)-X_\infty(\llcorner s\lrcorner _K)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} + c\left\lVert X_\infty(\llcorner s\lrcorner _K)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \end{align}\] and similarly that \[\begin{align} \begin{aligned} & \left\lVert {\mathbb{E}}[\sigma(x,X_\infty(s))]|_{x=X_\infty(s)} - {\mathbb{E}}[\sigma(y,X_K(\llcorner s\lrcorner _K))]|_{y=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^{d\times d})} \\ &\leq c\left\lVert X_\infty(s)-X_\infty(\llcorner s\lrcorner _K)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} + c\left\lVert X_\infty(\llcorner s\lrcorner _K)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}. \end{aligned} \end{align}\] This, the triangle inequality, Jensen’s inequality, Itô’s isometry, 15 , and the fact that \(c\geq 1\) imply for all \(K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \lVert X_K(t)-X_\infty(t)\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber \\ & = \sqrt{T}\left(\int_{0}^{t} \left\lVert {\mathbb{E}}[\mu(x,X_\infty(s))]|_{x=X_\infty(s)} - {\mathbb{E}}[\mu(y,X_K(\llcorner s\lrcorner _K))]|_{y=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds \right)^\frac{1}{2}\nonumber\\ &\quad + \left(\int_{0}^{t} \left\lVert {\mathbb{E}}[\sigma(x,X_\infty(s))]|_{x=X_\infty(s)} - {\mathbb{E}}[\sigma(y,X_K(\llcorner s\lrcorner _K))]|_{y=X_K(\llcorner s\lrcorner _K)}\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds \right)^\frac{1}{2}\nonumber\\ &\leq (\sqrt{T}+1)\Biggl[ c \left(\int_{0}^{t} \left\lVert X_\infty(s)-X_\infty(\llcorner s\lrcorner _K)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds \right)^\frac{1}{2}\nonumber\\ &\qquad \qquad\qquad + c\left(\int_{0}^{t}\left\lVert X_\infty(\llcorner s\lrcorner _K)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds\right)^\frac{1}{2} \Biggr]\nonumber\\ &\leq c\sqrt{T}(\sqrt{T}+1)\sqrt{T/K}\max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{3(\sqrt{T}+1)^2(T+1)c^2}\nonumber\\ &\quad +c(\sqrt{T}+1) \left(\int_{0}^{t}\left\lVert X_\infty(\llcorner s\lrcorner _K)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds\right)^\frac{1}{2}\nonumber\\ &\leq \sqrt{T/K} \max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{4(\sqrt{T}+1)^2(T+1)c^2}\nonumber\\&\quad +c(\sqrt{T}+1) \left(\int_{0}^{t}\left\lVert X_\infty(\llcorner s\lrcorner _K)- X_K(\llcorner s\lrcorner _K) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2ds\right)^\frac{1}{2}. \end{align}\] This and Grönwall’s inequality (cf., e.g., [62]) imply for all \(K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \lVert X_K(t)-X(t)\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber \\ &\leq \sqrt{2}\sqrt{T/K} \max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\} 3e^{4(\sqrt{T}+1)^2(T+1)c^2}e^{c^2(\sqrt{T}+1)^2T}\nonumber\\ &\leq 4.5 \sqrt{T/K} \max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu(0,0)\rVert, \lVert\sigma(0,0)\rVert\}e^{5(\sqrt{T}+1)^2(T+1)c^2} \end{align}\] This shows [a10] and completes the proof of 6. ◻
5 Proof of Theorem 1↩︎
In this section, we provide the proof of Theorem 1, which is divided into several steps. First, in Step [st02] we apply 6 to establish the existence, uniqueness, and upper bound of the exact solutions and the discretization error. In Step [s01] we establish measurability and distributional properties. In Step [s06] we prove the square-integrability of the approximations. In Step [s10] we consider the bias. In Step [s11] we consider the statistical error. In Step [s09] we obtain the global error. In Step [s08] we analyze the computational cost. In Step [s07] we analyze the computational complexity.
Throughout the proof we use the following notations. To lighten the notation, we denote by \({\mathbb{E}}_\mathcal{G}[\cdot]\) and \({\mathbb{V}}_\mathcal{G}[\cdot]\) the conditional expectation \({\mathbb{E}}[\cdot|\mathcal{G}]\) and the conditional variance \({\mathbb{V}}[\cdot|\mathcal{G}]\), respectively, i.e., we have for all \(d\in {\mathbb{N}}\) and all random variables \(X\colon \Omega\to{\mathbb{R}}^d\) that \({\mathbb{V}}_\mathcal{G}[X]= {\mathbb{E}}_\mathcal{G}\! \left[\left\lVert X- {\mathbb{E}}_{\mathcal{G}} [X]\right\rVert^2\right]\). Next, for every \(d,n,m,K\in {\mathbb{N}}\), let \(\mathcal{G}^d_{n,m,K}\) the sigma-algebra generated by \(W^{d,0}\), \(X^{d,0}_{\ell,m,K}\), \(\ell\in [0,n]\cap{\mathbb{Z}}\). Moreover, when applying a result we often use a phrase like “Lemma 3.8 with \(d\curvearrowleft(d-1)\)” that should be read as “Lemma 3.8 applied with \(d\) (in the notation of Lemma 3.8) replaced by \((d-1 )\) (in the current notation)”.
Proof of 1. We divide this proof into several steps.
Step . We establish the existence, uniqueness, and upper bound of the exact solutions and the discretization error. Observe that 6 (applied for every \(\theta\in \Theta\), \(d\in {\mathbb{N}}\) with \(T\curvearrowleft T\), \(c\curvearrowleft c\), \(d\curvearrowleft d\), \(\xi\curvearrowleft\xi_d\), \(\mu\curvearrowleft\mu_d\), \(\sigma\curvearrowleft\sigma_d\), \(W\curvearrowleft W^{d,\theta}\) in the notation of 6) and 2 show that the following items are true.
(A) For all \(K\in {\mathbb{N}}\cup\{\infty\}\), \(\theta\in \Theta\), \(d\in {\mathbb{N}}\) there exists a unique \({\mathbb{R}}^d\)-valued \(({\mathbb{F}}_t)_{t\in [0,T]}\)-adapted process \(X^{d,\theta}_K=(X^{d,\theta}_K(t))_{t\in [0,T]}\) with continuous sample paths such that we have \({\mathbb{P}}\)-a.s.for all \(t\in [0,T]\) that \(\sup_{s\in [0,T]}\lVert X_K^{d,\theta}(s)\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)}<\infty\) and \[\begin{align} X_K^{d,\theta}(t)&=\xi_d+\int_{0}^{t}{\mathbb{E}}\!\left[\mu(x,X^{d,\theta}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,\theta}_K(\llcorner s\lrcorner _K)}\,ds\nonumber\\ &\quad + \int_{0}^{t}{\mathbb{E}}\!\left[\sigma(x,X^{d,\theta}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,\theta}_K(\llcorner s\lrcorner _K)}\,dW^{d,\theta}(s).\label{a14} \end{align}\tag{16}\]
(B) For all \(t\in [0,T]\), \(K\in {\mathbb{N}}\cup\{\infty\}\), \(\theta\in \Theta\), \(d\in {\mathbb{N}}\) we have that \[\begin{align} \left\lVert X^{d,\theta}_K(t)\right\rVert_{L^2({\mathbb{P}},{\mathbb{R}}^d)} \leq \sqrt{2}\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu_d(0,0)\rVert,\lVert\sigma_d(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2t}.\label{a18} \end{align}\tag{17}\]
(C) For all \(K\in {\mathbb{N}}\), \(t\in [0,T]\), \(d\in {\mathbb{N}}\), \(\theta\in \Theta\) we have that \[\begin{align} &\left \lVert X^{d,\theta}_K(t)-X^{d,\theta}_\infty(t)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ & \leq 4.5 \sqrt{T/K} \max \{\lVert\xi_d\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}, \lVert\mu_d(0,0)\rVert, \lVert\sigma_d(0,0)\rVert\}e^{4(\sqrt{T}+1)(T+1)c^2}. \label{a15} \end{align}\tag{18}\]
Step . We establish measurability and distributional properties. First, the assumptions on measurability, basic facts on measurable functions, 4 , induction, and the fact that \(\forall\,d,K,m\in{\mathbb{N}},\theta\in\Theta\colon X_{0,m,K}^{d,\theta}=0\) prove for all \(d,K,m\in {\mathbb{N}}\), \(n\in{\mathbb{N}}_0\), \(\theta\in\Theta\) that \({X}_{n,m,K}^{d,\theta}: (\Omega,\mathcal{F}) \rightarrow {\mathbb{R}}^d\) defined in 4 is measurable. Next, the fact that \(\forall\,d,K,m\in{\mathbb{N}},\theta\in\Theta\colon X_{0,m,K}^{d,\theta}=0\), 4 , basic facts on sigma-algebras, and induction prove for all \(n\in{\mathbb{N}}_0\), \(d,K,m\in{\mathbb{N}}\), \(\theta\in\Theta\) that \[\begin{align} \begin{aligned} &\sigma\!\left(\left\{W^{d,\theta}(t),X^{d,\theta}_{\ell,m,K}(t) \colon \ell\in \{0,1,\ldots,n\},t\in [0,T]\right\}\right) \\ &\subseteq \sigma \!\left(\left\{W^{d,\theta}(t), W^{d,(\theta,i,\nu)}(t),\mathfrak{u}^{(\theta,i,\nu)}\colon i\in \{0,1,\ldots,n\},\nu\in\Theta, t\in[0,T] \right\} \right). \end{aligned}\label{a01v} \end{align}\tag{19}\] This and the fact that \(\forall\,d,K,m\in{\mathbb{N}},\theta\in\Theta\colon X_{0,m,K}^{d,\theta}=0\) prove for all \(n,m\in{\mathbb{N}}\), \(\theta\in\Theta\), \(k,\ell\in{\mathbb{N}}\), \(j\in\{\ell-1,\ell\}\) that \[\begin{align} \begin{aligned} &\sigma\!\left(\left\{X^{d,(\theta,n,k,\ell)}_{j,m,K}(t) \colon t\in [0,T]\right\}\right)\\ & \subseteq \sigma \!\left(\left\{W^{d,(\theta,n,k,\ell)}(t), W^{d,(\theta,n,k,\ell,\nu)}(t),\mathfrak{u}^{(\theta,n,k,\ell,\nu)}\colon\nu\in\Theta, t\in[0,T] \right\} \right). \end{aligned} \end{align}\] This, 19 , and the independence assumptions show for all \(d,K,n,m\in{\mathbb{N}}\), \(\theta\in\Theta\) that \[(W^{d,\theta},(X^{d,\theta}_{j,m,K})_{j\in [0,n-1]\cap{\mathbb{Z}}}),\quad (X^{d,(\theta,n,k,\ell)}_{\ell,m,K}, X^{d,(\theta,n,k,\ell)}_{\ell-1,m,K}),\quad \mathfrak{u}^{(\theta,n,k,\ell)},\quad k,\ell\in{\mathbb{N}},\] are independent. This, the fact that \(\forall\,d,K,m\in{\mathbb{N}},\theta\in\Theta\colon X_{0,m,K}^{d,\theta}=0\), 4 , the disintegration theorem (see, e.g., [63]), and induction show for all \(m\in{\mathbb{N}}\), \(n\in{\mathbb{N}}_0\) that \(( W^{d,\theta},(X_{\ell,m,K}^{d,\theta})_{ \ell\in\{0,1,\ldots,n\}} )\), \(\theta\in\Theta\), are identically distributed.
Step . We establish that the approximations are square-integrable. The triangle inequality, 2 , the distributional properties (see Step [s01]), and the disintegration theorem (see, e.g., [63]) prove for all \(d,m,n,K\in {\mathbb{N}}\), \(\ell \in [1,n-1]\cap{\mathbb{Z}}\), \(j\in \{\ell-1,\ell\}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert t \mu_d (X_{j,m,K}^{d,\theta} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K ),X_{j,m,K}^{d,(\theta,n,k,\ell)} (\llcorner t\mathfrak{u}^{(\theta,n,k,\ell)}\lrcorner _K ))\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ & =\sqrt{t}\left(\int_{0}^{t} \left\lVert \mu_d (X_{j,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{j,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K )) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 ds\right)^\frac{1}{2}\nonumber\\ & \leq T\left\lVert\mu_d(0,0)\right\rVert+ c\sqrt{T} \left(\int_{0}^{T} \left \lVert X^{d,0}_{j,m,K}(\llcorner s\lrcorner _K) ) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 ds\right)^\frac{1}{2}\nonumber\\ &\leq T\left\lVert\mu_d(0,0)\right\rVert+ cT\sup_{s\in [0,T]} \left \lVert X^{d,0}_{j,m,K}(s) ) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}.\label{r02} \end{align}\tag{20}\] Next, Itô’s isometry, the triangle inequality, 2 , the distributional properties (see Step [s01]), and the disintegration theorem (see, e.g., [63]) imply for all \(d,m,n,K\in {\mathbb{N}}\), \(\ell \in [1,n-1]\cap{\mathbb{Z}}\), \(j\in \{\ell-1,\ell\}\), \(t\in [0,T]\) that \[\begin{align} &\left\lVert \int_{0}^{t} \sigma_d (X_{j,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{j,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K ))\, dW^{d,\theta}(s) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \nonumber\\ &=\left(\int_{0}^{t} \left\lVert \sigma_d(X_{j,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{j,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K )) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^{d\times d})}^2 ds\right)^\frac{1}{2}\nonumber\\ & \leq \sqrt{T}\left\lVert\sigma_d(0,0)\right\rVert+ c \left(\int_{0}^{T} \left \lVert X^{d,0}_{j,m,K}(\llcorner s\lrcorner _K) ) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 ds\right)^\frac{1}{2}\nonumber\\ &\leq \sqrt{T}\left\lVert\sigma_d(0,0)\right\rVert+ c\sqrt{T}\sup_{s\in [0,T]} \left \lVert X^{d,0}_{j,m,K}(s) ) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}.\label{r03} \end{align}\tag{21}\] This, the fact that \(\forall\, d,k,m\in {\mathbb{N}}, \theta\in \Theta\colon X^{d,\theta}_{0,m,K}=0\), 4 , the triangle inequality, and induction show for all \(d,n,m,K\in {\mathbb{N}}\), \(\ell\in [1,n-1]\cap{\mathbb{Z}}\), \(j\in \{\ell-1,\ell\}\) that \[\begin{align} \small\begin{aligned} & \sup_{t\in[0,T]}\Biggl[ \left\lVert X_{n,m,K}^0(t)\right\rVert^2_{L^2({\mathbb{P}};{\mathbb{R}}^d)}+ \left\lVert \mu\bigl(X^0_{j,m,K}(t \mathfrak{u}^{(0,n,k,\ell)}), X^{(0,n,k,\ell)}_{j,m,K}(t \mathfrak{u}^{(0,n,k,\ell)}) \bigr)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \\ &\qquad\qquad\qquad + \left\lVert \int_{0}^{t} \sigma_d (X_{j,m,K}^{d,\theta} (\llcorner s\lrcorner _K ),X_{j,m,K}^{d,(\theta,n,k,\ell)} (\llcorner s\lrcorner _K ))\, dW^{d,\theta}(s) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \Biggr]<\infty.\end{aligned} \end{align}\]
Step . We analyze for all \(d,n,m,K\in {\mathbb{N}}\) the bias of \(X^{d,0}_{n,m,K}\). Recall for every \(d,n,m,K\in {\mathbb{N}}\) that \(\mathcal{G}^d_{n,m,K}\) is the sigma-algebra generated by \(W^{d,0}\), \(X^{d,0}_{\ell,m,K}\), \(\ell\in [0,n]\cap{\mathbb{Z}}\). Integrability (see Step [s06]), linearity of the conditional expectations, the distributional properties (see Step [s01]), the disintegration theorem (see, e.g., [63]), and the fact that \(\forall m,d,K\in {\mathbb{N}}\colon X^{d,0}_{0,m,K}=0\) show for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} &{\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}}\!\left[ X^{d,0}_{n,m,K}(t)\right]\nonumber\\ &= \xi_d +t\mu_d(0,0)+\sigma_d(0,0)W^{d,0}(t)\nonumber\\ &\qquad+ \sum_{\ell=1}^{n-1}\sum_{k=1}^{m^{n-\ell}} \frac{t}{m^{n-\ell}} {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ),X_{\ell,m,K}^{d,(0,n,k,\ell)} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ),X_{\ell-1,m,K}^{d,(0,n,k,\ell)} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K )) \Bigr]\nonumber \\ &\qquad+ \sum_{\ell=1}^{n-1}\sum_{k=1}^{m^{n-\ell}}\int_{0}^{t} \frac{1}{m^{n-\ell}}{\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \sigma_d(X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,(0,n,k,\ell)} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad\qquad - \sigma_d(X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,(0,n,k,\ell)} (\llcorner s\lrcorner _K ))\Bigr] dW^{d,0}(s)\nonumber\\ &= \xi_d +t\mu_d(0,0)+\sigma_d(0,0)W^{d,0}(t)\nonumber\\ &\qquad+ \sum_{\ell=1}^{n-1} t {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K )) \Bigr]\nonumber \\ &\qquad+ \sum_{\ell=1}^{n-1}\int_{0}^{t} {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \sigma_d(X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad\qquad - \sigma_d(X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K ))\Bigr] dW^{d,0}(s)\nonumber\\ &= \xi_d +t\mu_d(0,0)+\sigma_d(0,0)W^{d,0}(t)\nonumber\\ &\qquad+ \sum_{\ell=1}^{n-1} \int_{0}^{t} {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \mu_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \Bigr]ds\nonumber \\ &\qquad+ \sum_{\ell=1}^{n-1}\int_{0}^{t} {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ \sigma_d(X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad\qquad - \sigma_d(X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K ))\Bigr] dW^{d,0}(s)\nonumber\\ &=\xi_d+ \int_{0}^{t} {\mathbb{E}}\!\left[\mu_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)}\,ds\nonumber\\ &\qquad + \int_{0}^{t} {\mathbb{E}}\!\left[\sigma_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)}\,dW^{d,0}(s). \end{align}\] This and 16 prove for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}}\!\left[ X^{d,0}_{n,m,K}(t)\right]- X_K^{d,0}(t)\nonumber\\ &= \int_{0}^{t} {\mathbb{E}}\!\left[\mu_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)} -{\mathbb{E}}\!\left[\mu(x,X^{d,0}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_K(\llcorner s\lrcorner _K)} \,ds\nonumber\\ & + \int_{0}^{t} {\mathbb{E}}\!\left[\sigma_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)}-{\mathbb{E}}\!\left[\sigma(x,X^{d,0}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_K(\llcorner s\lrcorner _K)}\,dW^{d,0}(s). \end{align}\] This, the triangle inequality, Jensen’s inequality, Itô’s isometry, 2 , and the disintegration theorem (see, e.g., [63]) show for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}}\!\left[ X^{d,0}_{n,m,K}(t)\right]- X_K^{d,0}(t)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \nonumber\\ &\leq \sqrt{T}\Biggl( \int_{0}^{t} \Bigl\lVert {\mathbb{E}}\!\left[\mu_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)}\nonumber\\ &\qquad\qquad -{\mathbb{E}}\!\left[\mu_d(x,X^{d,0}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_K(\llcorner s\lrcorner _K)}\Bigr\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 \,ds\Biggr)^\frac{1}{2}\nonumber\\ & +\Biggl( \int_{0}^{t} \Bigl\lVert {\mathbb{E}}\!\left[\sigma_d (x,X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)}\nonumber\\ &\qquad\qquad-{\mathbb{E}}\!\left[\sigma_d(x,X^{d,0}_K(\llcorner s\lrcorner _K))\right]\!|_{x=X^{d,0}_K(\llcorner s\lrcorner _K)}\Bigr \rVert^2_{L^2({\mathbb{P}};{\mathbb{R}}^{d\times d})}ds \Biggr)^\frac{1}{2} \nonumber\\ &\leq (\sqrt{T}+1)c \left(\int_{0}^{t}\left\lVert X^{d,0}_{n-1,m,K}(\llcorner s\lrcorner _K)-X^{d,0}_{K}(\llcorner s\lrcorner _K)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2 ds\right)^\frac{1}{2}.\label{b01} \end{align}\tag{22}\]
Step . We consider the statistical error. The distributional properties (cf.Step [s01]) imply for all \(d,K,n,m\in{\mathbb{N}}\), \(\ell\in [1,n-1]\cap{\mathbb{N}}\) that
(A) we have that \((X^{d,(0,n,1,\ell)}_{\ell,m,K}, X^{d,(0,n,1,\ell)}_{\ell-1,m,K}, \mathfrak{u}^{(0,n,1,\ell)})\) and \(\mathcal{G}^d_{n-1,m,K}\) are independent,
(B) we have \({\mathbb{P}}\)-a.s.that \((X^{d,(0,n,k,\ell)}_{\ell,m,K}, X^{d,(0,n,k,\ell)}_{\ell-1,m,K}, \mathfrak{u}^{(0,n,k,\ell)})\), \(k\in{\mathbb{N}}\), are i.i.d. under \({\mathbb{P}}[\cdot |\mathcal{G}^d_{n-1,m,K}]\), and
(C) we have that \(((X^{d,(0,n,1,\ell)}_{\ell,m,K}, X^{d,(0,n,1,\ell)}_{\ell-1,m,K})\) and \(((X^{d,0}_{\ell,m,K}, X^{d,0}_{\ell-1,m,K})\) are identically distributed.
This, 4 , the triangle inequality, Bienaymé’s identity, the assumptions on distributions, and the disintegration theorem (see, e.g., [63]) prove that for all \(d,K,n,m\in{\mathbb{N}}\), \(t\in [0,T]\) we have \({\mathbb{P}}\)-a.s. that \[\begin{align} &\left({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\!\left [ X^{d,0}_{n,m,K}(t)\right]\right)^\frac{1}{2} \nonumber\\ &= \sum_{\ell=1}^{n-1}\Biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\Biggl[ \sum_{k=1}^{m^{n-\ell}} \frac{t}{m^{n-\ell}} \Bigl[ \mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ),X_{\ell,m,K}^{d,(0,n,k,\ell)} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K ),X_{\ell-1,m,K}^{d,(0,n,k,\ell)} (\llcorner t\mathfrak{u}^{(0,n,k,\ell)}\lrcorner _K )) \Bigr]\Biggr]\Biggr)^\frac{1}{2}\nonumber \\ &\quad + \sum_{\ell=1}^{n-1}\Biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\Biggl[\sum_{k=1}^{m^{n-\ell}}\int_{0}^{t} \frac{1}{m^{n-\ell}} \Bigl[ \sigma_d(X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,(0,n,k,\ell)} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad\qquad - \sigma_d(X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,(0,n,k,\ell)} (\llcorner s\lrcorner _K ))\Bigr] dW^{d,0}(s)\Biggr]\Biggr)^\frac{1}{2}\nonumber\\ &=\sum_{\ell=1}^{n-1}\Biggl[\frac{1}{\sqrt{m^{n-\ell}}} \biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ t\mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - t\mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K )) \Bigr]\biggr)^\frac{1}{2}\Biggr]\nonumber\\ &\quad +\sum_{\ell=1}^{n-1}\Biggl[\frac{1}{\sqrt{m^{n-\ell}}} \biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\biggl[\int_{0}^{t} \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber \\ &\qquad\qquad\qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \,dW^{d,0}(s) \biggr]\biggr)^\frac{1}{2}\Biggr].\label{a16} \end{align}\tag{23}\] Next, a property of conditional expectations, the disintegration theorem (see, e.g., [63]), the distributional properties (see Step [s01]), the fact that for all \(t\in [0,T]\) we have that \(t\mathfrak{u}^1\) is uniformly distributed on \([0,t]\), and 2 show for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\), \(\ell\in [1,n-1]\) that \[\begin{align} &\biggl \lVert\biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[ t\mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - t\mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K )) \Bigr]\biggr)^\frac{1}{2}\biggr \rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber \\ &\leq \biggl \lVert\biggl({\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[\Bigl \lVert t\mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - t\mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\Bigr \rVert^2 \Bigr]\biggr)^\frac{1}{2}\biggr \rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber\\ &\leq \Biggl( {\mathbb{E}}\biggl[{\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}} \Bigl[\Bigl \lVert t\mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - t\mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\Bigr \rVert^2 \Bigr]\biggr]\Biggr)^\frac{1}{2}\nonumber\\ &= \Biggl( {\mathbb{E}}\biggl[\Bigl \lVert t\mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - t\mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\Bigr \rVert^2\biggr]\Biggr)^\frac{1}{2}\nonumber\\ &\leq \sqrt{T} \Biggl( {\mathbb{E}}\biggl[t\Bigl \lVert \mu_d (X_{\ell,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner t\mathfrak{u}^{1}\lrcorner _K ))\Bigr \rVert^2\biggr]\Biggr)^\frac{1}{2}\nonumber\\ &=\sqrt{T} \Biggl( {\mathbb{E}}\biggl[\int_{0}^{t}\Bigl \lVert \mu_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \mu_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K ))\Bigr \rVert^2ds\biggr]\Biggr)^\frac{1}{2}\nonumber\\ &\leq c\sqrt{T}\left({\mathbb{E}}\!\left[\int_{0}^{t}\left\lVert X^{d,0}_{\ell,m,K}(\llcorner s\lrcorner _K)- X^{d,0}_{\ell-1,m,K}(\llcorner s\lrcorner _K)\right \rVert^2ds\right] \right)^\frac{1}{2}\nonumber\\ &\leq c\sqrt{T}\sum_{j=\ell-1}^{\ell}\left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{j,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}. \end{align}\] Similarly but using Itô’s formula we have for all \(d,K,n,m\in{\mathbb{N}}\), \(t\in [0,T]\), \(\ell\in [1,n-1]\cap{\mathbb{Z}}\) that, \({\mathbb{P}}\)-a.s., \[\begin{align} &\Biggl\lVert \biggl({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\biggl[\int_{0}^{t} \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber \\ &\qquad\qquad\qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \,dW^{d,0}(s) \biggr]\biggr)^\frac{1}{2} \Biggr\rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber \\ & \leq \Biggl\lVert \biggl({\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}}\biggl[\biggl\lVert\int_{0}^{t} \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \,dW^{d,0}(s)\biggr\rVert^2 \biggr]\biggr)^\frac{1}{2}\Biggr\rVert_{L^2({\mathbb{P}};{\mathbb{R}})}\nonumber\\ &= \Biggl({\mathbb{E}}\biggl[ {\mathbb{E}}_{\mathcal{G}^d_{n-1,m,K}}\biggl[\biggl\lVert\int_{0}^{t} \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \,dW^{d,0}(s)\biggr\rVert^2\biggr] \biggr]\Biggr)^\frac{1}{2}\nonumber\\ &\leq \Biggl({\mathbb{E}} \Biggl[\biggl\lVert\int_{0}^{t} \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad \qquad \qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \,dW^{d,0}(s)\biggr\rVert^2 \Biggr]\Biggr)^\frac{1}{2}\nonumber \\ &=\biggl( \int_{0}^{t} {\mathbb{E}}\biggl[ \Bigl\lVert \sigma_d (X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell,m,K}^{d,1} (\llcorner s\lrcorner _K ))\nonumber\\ &\qquad\qquad\qquad\qquad - \sigma_d (X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ),X_{\ell-1,m,K}^{d,1} (\llcorner s\lrcorner _K )) \Bigr\rVert^2 \biggr]ds\biggr)^\frac{1}{2}\nonumber \\ &\leq c\left( \int_{0}^{t} \left\lVert X_{\ell,m,K}^{d,0} (\llcorner s\lrcorner _K ) -X_{\ell-1,m,K}^{d,0} (\llcorner s\lrcorner _K ) \right\rVert^2ds\right)^\frac{1}{2} \nonumber\\ &\leq c\sum_{j=\ell-1}^{\ell}\left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{j,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}.\label{a17} \end{align}\tag{24}\]
Step .We combine the bias, the statistical error, and the discretization error to obtain the global error and to show for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert X^{d,0}_{n,m,K}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \sqrt{2}(\sqrt{T}+1)cd^ce^{(\sqrt{T}+1)^2c^2T} e^{2nc(\sqrt{T}+1)\sqrt{T} }\frac{e^{m/2}}{m^{n/2}} +4.5 \sqrt{T/K}cd^ce^{4(\sqrt{T}+1)(T+1)c^2}. \label{a19c} \end{align}\tag{25}\] Combining 23 –24 , properties of conditional expectations, and the triangle inequality we have for all \(d,n,m,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert X^{d,0}_{n,m,K}(t)- {\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} }\!\left[ X^{d,0}_{n,m,K}(t)\right] \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}^2\nonumber\\ & ={\mathbb{E}}\!\left[ \left\lVert X^{d,0}_{n,m,K}(t)- {\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} }\!\left[ X^{d,0}_{n,m,K}(t)\right] \right\rVert^2\right]\nonumber\\ &={\mathbb{E}}\left[{\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} } \!\left[ \left\lVert X^{d,0}_{n,m,K}(t)- {\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} }\!\left[ X^{d,0}_{n,m,K}(t)\right] \right\rVert^2\right] \right]\nonumber\\ &={\mathbb{E}}\!\left[{\mathbb{V}}_{\mathcal{G}^{d}_{n-1,m,K}\! }\left[X^{d,0}_{n,m,K}(t)\right]\right]\nonumber\\ &= \left\lVert \left({\mathbb{V}}_{\mathcal{G}^d_{n-1,m,K}}\!\left [ X^{d,0}_{n,m,K}(t)\right]\right)^\frac{1}{2} \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}})} \nonumber\\ &\leq \sum_{\ell=1}^{n-1} \frac{1}{\sqrt{m^{n-\ell}}}c(\sqrt{T}+1)\sum_{j=\ell-1}^{\ell}\left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{j,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}\nonumber\\ &\leq \sum_{\ell=0}^{n-1} \frac{(2-{\mathbb{1}}_{\{n-1\}}(\ell))c(\sqrt{T}+1)}{\sqrt{m^{n-\ell-1}}} \left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{\ell,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}. \end{align}\] This, the triangle inequality, and 22 prove for all \(d,n,m,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert X^{d,0}_{n,m,K}(t)-X_K^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ & \leq \left\lVert X^{d,0}_{n,m,K}(t)- {\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} }\!\left[ X^{d,0}_{n,m,K}(t)\right] \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} + \left\lVert {\mathbb{E}}_{\mathcal{G}^{d}_{n-1,m,K} }\!\left[ X^{d,0}_{n,m,K}(t)\right] -X_K^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \sum_{\ell=0}^{n-1} \frac{2c(\sqrt{T}+1)}{\sqrt{m^{n-\ell-1}}} \left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{\ell,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}. \end{align}\] This and the monotonicity of the integral show for all \(d,n,m,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} &\sup_{u\in[0,t]} \left\lVert X^{d,0}_{n,m,K}(u)-X_K^{d,0}(u) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \sum_{\ell=0}^{n-1} \frac{2c(\sqrt{T}+1)}{\sqrt{m^{n-\ell-1}}} \left( \int_{0}^{t}\sup_{r\in [0,s]}\left\lVert X^{d,0}_{\ell,m,K}(r)-X^{d,0}_K(r)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} ^2\,ds \right)^\frac{1}{2}. \end{align}\] This, [64], 17 , the fact that \(\forall\, d,m,K\colon X^{d,0}_{0,m,K}=0\), and 3 show for all \(n,m,d,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \sup_{u\in[0,t]} \left\lVert X^{d,0}_{n,m,K}(u)-X_K^{d,0}(u) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \nonumber \\ & \leq \left(2c(\sqrt{T}+1)T^{1/2} \sup_{t\in [0,T]} \left\lVert X^{d,0}_{K}(t)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \right) \left[\max_{k\in\{0,1,\ldots,n\}} \frac{1}{\sqrt{m^{n-k}k!}}\right] \left(1+2c(\sqrt{T}+1)T^{1/2}\right)^{n-1}\nonumber\\ &\leq \left( \sup_{t\in [0,T]} \left\lVert X^{d,0}_{K}(t)\right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} \right)\left(1+2c(\sqrt{T}+1)T^{1/2}\right)^{n} \left[\max_{k\in\{0,1,\ldots,n\}} \frac{\sqrt{m^k}}{\sqrt{m^{n}k!}}\right]\nonumber\\ &\leq \sqrt{2}\left( \lVert\xi_d\rVert+(\sqrt{T}+1) \max\{\lVert\mu_d(0,0)\rVert,\lVert\sigma_d(0,0)\rVert\} \right)e^{(\sqrt{T}+1)^2c^2T} e^{2nc(\sqrt{T}+1)\sqrt{T} }\frac{e^{m/2}}{m^{n/2}}\nonumber\\ &\leq \sqrt{2}(\sqrt{T}+1)cd^ce^{(\sqrt{T}+1)^2c^2T} e^{2nc(\sqrt{T}+1)\sqrt{T} }\frac{e^{m/2}}{m^{n/2}}. \end{align}\] This, the triangle inequality, and 18 show for all \(d,m,n,K\in {\mathbb{N}}\), \(t\in [0,T]\) that \[\begin{align} & \left\lVert X^{d,0}_{n,m,K}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ & \leq \left\lVert X^{d,0}_{n,m,K}(t)-X_K^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)} + \left\lVert X_K^{d,0}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\nonumber\\ &\leq \sqrt{2}(\sqrt{T}+1)cd^ce^{(\sqrt{T}+1)^2c^2T} e^{2nc(\sqrt{T}+1)\sqrt{T} }\frac{e^{m/2}}{m^{n/2}} +4.5 \sqrt{T/K}cd^ce^{4(\sqrt{T}+1)(T+1)c^2}.\label{c04} \end{align}\tag{26}\] This shows 25 .
Step .We analyze the computational cost. Recall that \(\mathsf{C}^d_{n,m,K}\) the computational cost to construct the whole discrete process \((X_{n,m,K}^\theta(\frac{kT}{K}))_{k\in [1,K]\cap{\mathbb{Z}}}\) given that we have prepared a discrete Brownian path \(W^\theta(\frac{kT}{K}))_{k\in [1,K]\cap{\mathbb{Z}}}\). Note that by definition for all \(d,n,m,K\in {\mathbb{N}}\) the cost \(\mathsf{C}^d_{n,m,K}\) contains the following costs:
The cost to calculate \(\mu_d(0,0)\) is \(\mathsf{cost}_{\mu_d}\).
The cost to calculate \(\sigma_d(0,0)\) is \(\mathsf{cost}_{\sigma_d}\).
For each \(\ell \in [1,n-1]\cap{\mathbb{Z}}\), \(k\in [1,m^{n-\ell}]\cap{\mathbb{Z}}\):
We need to prepare two processes \(X^{d,\theta}_{\ell,m,K}\) and \(X^{d,\theta}_{\ell-1,m,K}\), which brings the cost \(\mathsf{C}^d_{\ell,m,K}+\mathsf{C}^d_{\ell-1,m,K}\).
We need to prepare two processes \(X^{d,(\theta,n,k,\ell)}_{\ell,m,K}\) and \(X^{d,(\theta,n,k,\ell)}_{\ell-1,m,K}\), which come from a new source of Brownian randomness, which brings the cost \(\mathsf{C}^d_{\ell,m,K}+\mathsf{C}^d_{\ell-1,m,K}+ Kd\mathsf{cost}_{\mathsf{rv}}\). Here, \(Kd\) is the size of the Brownian motion and \(\mathsf{cost}_{\mathsf{rv}}\) is the cost to generate a scalar random variable.
We need to prepare a scalar random variable, \(\mathfrak{u}^{(\theta,n,k,\ell)}\), which brings the cost \(\mathsf{cost}_\mathsf{rv}\)
We need to evaluate \(\mu\) at two points which brings the cost \(2\mathsf{cost}_{\mu_d}\)
We need to evaluate \(\sigma_d\) at each point of the two processes \(((X_{\ell,m,K}^{d,\theta} (\frac{kT}{T} ),X_{\ell,m,K}^{d,(\theta,n,k,\ell)} (\frac{kT}{T} )))_{k\in [1,K]}\) and \(((X_{\ell-1,m,K}^{d,\theta} (\frac{kT}{T} ),X_{\ell-1,m,K}^{d,(\theta,n,k,\ell)} (\frac{kT}{T} )))_{k\in [1,K]}\) which brings the cost \(2K\mathsf{cost}_{\sigma_d}\)
To summary we have for all \(d,m,n,K\in {\mathbb{N}}\) that \[\begin{align} \begin{aligned} \mathsf{C}^d_{n,m,K}\leq \mathsf{cost}_{\mu_d}+\mathsf{cost}_{\sigma_d}+\sum_{\ell=1}^{n-1}m^{n-\ell}\Bigl(& (\mathsf{C}^d_{\ell,m,K} + \mathsf{C}^d_{\ell-1,m,K}) + (\mathsf{C}^d_{\ell,m,K} + \mathsf{C}^d_{\ell-1,m,K}+Kd\mathsf{cost}_{\mathsf{rv}})\\ &+\mathsf{cost}_\mathsf{rv}+2\mathsf{cost}_{\mu_d}+2K\mathsf{cost}_{\sigma_d}\Bigr).\end{aligned} \end{align}\] This and 5 show for all \(n,m,d,K\in {\mathbb{N}}\) that \[\begin{align} \mathsf{C}^d_{n,m,K}\leq cd^c+ \sum_{\ell=1}^{n-1} m^{n-\ell} \left(2\mathsf{C}^d_{\ell,m,K}+2\mathsf{C}^d_{\ell-1,m,K}+cd^c2Kd\right) \end{align}\] and hence \[\begin{align} m^{-n} \mathsf{C}^d_{n,m,K} &\leq cd^cm^{-n} +\sum_{\ell=1}^{n-1}\left( 2m^{-\ell} \mathsf{C}^d_{\ell,m,K} +2m^{-(\ell-1)} \mathsf{C}^d_{\ell-1,m,K}+2cd^cKd\right)\nonumber\\ &= cd^cm^{-n} +2cd^cKdn +\sum_{\ell=1}^{n-1}\left( 2m^{-\ell} \mathsf{C}^d_{\ell,m,K} +2m^{-(\ell-1)} \mathsf{C}^d_{\ell-1,m,K}\right). \end{align}\] This, the fact that \(\forall\,d,m,K\colon\mathsf{C}^d_{0,m,K}=0\), and [49] (applied for every \(d,m,K\in {\mathbb{N}}\) with \((a_n)_{n\in {\mathbb{N}}_0} \curvearrowleft(m^{-n} \mathsf{C}^d_{n,m,K})_{n\in {\mathbb{N}}_0}\), \(\kappa\curvearrowleft 2\), \(\lambda\curvearrowleft 2\) \(c_1\curvearrowleft cd^c\), \(c_2\curvearrowleft 2cd^cKd\), \(c_3\curvearrowleft 0\), \(c_4\curvearrowleft 0\), \(\beta\curvearrowleft\frac{1+2+\sqrt{(1+2)^2+4\cdot 2}}{2}\) in the notation of [49]) show for all \(d,m,n,K\in {\mathbb{N}}\) that \[\begin{align} m^{-n} \mathsf{C}^d_{n,m,K}\leq \frac{3}{2}4^ncd^c+\frac{3\cdot2cd^cKd(4^n-1)}{2(4-1)} \leq \frac{3}{2}4^ncd^c+4^ncd^cKd\leq 8^ncd^cKd . \end{align}\] and hence \(\mathsf{C}^d_{n,m,K}\leq (8m)^ncd^cKd\). Therefore, for all \(n,d\in {\mathbb{N}}\) we have that \[\begin{align} \label{c15} \mathsf{C}^d_{n,n,n^n}\leq (8n)^ncd^cn^nd\leq (8n)^{2n}cd^{c+1} \end{align}\tag{27}\] and hence \[\begin{align} \mathsf{C}^d_{n+1,n+1,(n+1)^{(n+1)}}\leq [8(n+1)]^{2(n+1)}cd^{c+1}\leq (16n)^{2n+2}cd^{c+1} =16^{2n+2}n^2n^{2n}cd^{c+1}.\label{c11} \end{align}\tag{28}\]
Step .We analyze the computational complexity. For every \(d\in {\mathbb{N}}\), \(\epsilon\in (0,1)\) let \[\begin{align} \mathsf{n}_{d,\epsilon} =\inf\!\left(\left \{ n\in {\mathbb{N}}\colon \sup_{k\in [n,\infty)\cap{\mathbb{Z}}} \sup _{t\in [0,T]} \left\lVert X^{d,0}_{k,k,k^k}(t)-X^{d,0}_\infty(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}<\epsilon \right\}\cup\{\infty\}\right).\label{c16} \end{align}\tag{29}\] Next, 25 shows that there exists \(C\in [1,\infty)\) such that for all \(d,n\in {\mathbb{N}}\) we have that \[\begin{align} \left\lVert X^{d,0}_{n,n,n^n}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\leq \frac{2cd^cC^ne^{n/2}}{n^{n/2}}.\label{c13} \end{align}\tag{30}\] This proves for all \(d\in {\mathbb{N}}\) that \[\begin{align} \lim_{n\to\infty} \left\lVert X^{d,0}_{n,n,n^n}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}=0. \end{align}\] Therefore, for all \(d\in {\mathbb{N}}\), \(\epsilon\in (0,1)\) we have that \(\mathsf{n}_{d,\epsilon}\in {\mathbb{N}}\). Next, for every \(\delta\in (0,1)\) let \[\begin{align} \mathfrak{C}_\delta =c^6 \sup_{n\in{\mathbb{N}}} \left[16^{2n+2}n^2(2C^ne^{n/2})^{5}n^{-\delta n/2}\right].\label{c14} \end{align}\tag{31}\] Observe for all \(\delta\in (0,1)\) that there exist \(\gamma\in (0,\infty)\) such that \(\mathfrak{C}_\delta<32\cdot 16^2n^2\gamma^nn^{-\delta n/2}\). Since \((n^{\delta n/2})_{n\in {\mathbb{N}}}\) increases faster than any exponential function, we obtain that \(\mathfrak{C}_\delta<\infty\) for all \(\delta\in (0,1)\). Then 28 and 30 show for all \(d,n\in {\mathbb{N}}\), \(\delta\in (0,1)\) that \[\begin{align} & \mathsf{C}^d_{n+1,n+1,(n+1)^{(n+1)}} \left( \sup_{t\in [0,T]}\left\lVert X^{d,0}_{n,n,n^n}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\right)^{4+\delta} \nonumber\\ &\leq 16^{2n+2}n^2n^{2n}cd^{c+1}\left(\frac{2cd^cC^ne^{n/2}}{n^{n/2}} \right)^{4+\delta}\nonumber\\ &\leq (cd^{c+1})^6\left[16^{2n+2}n^2(2C^ne^{n/2})^{5}n^{-\delta n/2}\right]\nonumber\\ &\leq (d^{c+1})^6\mathfrak{C}_\delta <\infty.\label{c17} \end{align}\tag{32}\] This, 29 , 27 , 31 , and the fact that \(C\geq 1\) show for all \(d\in {\mathbb{N}}\), \(\epsilon,\delta\in (0,1)\) that \[\begin{align} & \mathsf{C}_{\mathsf{n}_{d,\epsilon},\mathsf{n}_{d,\epsilon}, (\mathsf{n}_{d,\epsilon})^{\mathsf{n}_{d,\epsilon}}}^d\epsilon^{4+\delta}\nonumber\\ &\leq{\mathbb{1}}_{\{1\}}(\mathsf{n}_{d,\epsilon})\mathsf{C}^d_{1,1,1} +{\mathbb{1}}_{[2,\infty)} (\mathsf{n}_{d,\epsilon}) \mathsf{C}_{\mathsf{n}_{d,\epsilon},\mathsf{n}_{d,\epsilon}, (\mathsf{n}_{d,\epsilon})^{\mathsf{n}_{d,\epsilon}}}^d \left( \sup_{t\in [0,T]}\left\lVert X^{d,0}_{n,n,n^n}(t)-X_\infty^{d,0}(t) \right\rVert_{L^2({\mathbb{P}};{\mathbb{R}}^d)}\right)^{4+\delta}|_{n=\mathsf{n}_{d,\epsilon}-1}\nonumber\\ &\leq{\mathbb{1}}_{\{1\}}(\mathsf{n}_{d,\epsilon}) 64 cd^{c+1}+ {\mathbb{1}}_{[2,\infty)} (\mathsf{n}_{d,\epsilon}) (d^{c+1})^6\mathfrak{C}_\delta\nonumber\\ &\leq (d^{c+1})^6\mathfrak{C}_\delta.\label{c18} \end{align}\tag{33}\] This, the fact that \(\forall\,\delta\in (0,1)\colon \mathfrak{C}_\delta<\infty\), and 29 show [c19]. The proof of 1 is thus completed. ◻
References↩︎
Let \(T \in [0,\infty)\) and \({\boldsymbol{\Omega}} = (\Omega,\mathcal{F},{\mathbb{P}}, ({\mathbb{F}}_t)_{t\in[0,T]})\) be a filtered probability space. We say that \({\boldsymbol{\Omega}}\) satisfies the usual conditions if and only if \(\{ A \subseteq \Omega: \exists N \in \mathcal{F} \text{ with } A \subseteq N \text{ and } {\mathbb{P}}(N) = 0 \} \subseteq {\mathbb{F}}_0\) and \(\forall \, t\in [0,T) \colon \mathbb{F}_t = \cap_{ s \in (t,T] } {\mathbb{F}}_s\).↩︎
The numerical experiments have been implemented in
Pythonand executed on a HPC cluster of D-MATH, ETH Zurich. The code is available under the following link: https://github.com/psc25/McKeanVlasovMLP.↩︎