Abstract
We discuss numerical aspects related to a new class of NonLinear Stochastic Differential Equation (NLSDE) in the sense of McKean, which are supposed to represent non conservative nonlinear Partial Differential Equations (PDEs). We propose an original interacting particle system for which we discuss the propagation of chaos. We consider a time-discretized approximation of this particle system to which we associate a random function which is proved to converge to a solution of a regularized version of a nonlinear PDE.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Stochastic differential equations of various types are very useful to investigate nonlinear Partial Differential Equations (PDEs) at the theoretical and numerical level. From a theoretical point of view, they constitute probabilistic tools to study the analytic properties of the equation. Moreover they provide a microscopic interpretation of physical phenomena macroscopically drawn by a nonlinear PDE. From a numerical point of view, such representations allow for extended Monte Carlo type methods, which are potentially less sensitive to the dimension of the state space.
Let us consider \(d,p \in \mathbb N^{\star }\). Let \(\Phi :[0,T] \times \mathbb R^d \times \mathbb R\rightarrow \mathbb R^{d \times p}\), \(g:[0,T] \times \mathbb R^d \times \mathbb R\rightarrow \mathbb R^d\), \(\Lambda :[0,T] \times \mathbb R^d \times \mathbb R\rightarrow \mathbb R\), be Borel bounded functions, \(K: \mathbb R^d \rightarrow \mathbb R\) be a smooth mollifier in \(\mathbb R^d\) and \(\zeta _0\) be a probability on \(\mathbb R^d\). When it is absolutely continuous \(v_0\) will denote its density so that \(\zeta _0(dx) = v_0(x) dx\). The main motivation of this work is the simulation of solutions to PDEs of the form
through probabilistic numerical methods. Examples of nonlinear and nonconservative PDEs that are of that form arise in hydrodynamics and biological modeling. For instance one model related to underground water flows is known in the literature as the Richards equation
where \(\beta : \mathbb R\longrightarrow \mathbb R, \ \alpha : \mathbb R\longrightarrow \mathbb R^d \) and \(\phi : \mathbb R^d \longrightarrow \mathbb R\). Another example concerns biological mechanisms as migration of biologial species or the evolution of a tumor growth. Such equations can be schematically written as
where \(\beta : \mathbb R\longrightarrow \mathbb R\) is bounded, monotone and \(f : \mathbb R\rightarrow \mathbb R\). This family of PDEs is sometimes called Porous Media type Equation with proliferation, due to the presence of the term f that characterizes a proliferation phenomena and the term \(\Delta \beta (v)\) delineates a porous media effect. In particular, for \(\beta (v) = v^2\) and \(f(v) = v(1-v)\), this type of equation appears in the modeling of tumors.
The present paper focuses on numerical aspects of a specific forward probabilistic representation initiated in [20], relying on nonlinear SDEs in the sense of McKean [21]. In [20], we have introduced and studied a generalized regularized McKean type NonLinear Stochastic Differential Equation (NLSDE) of the form
where the solution is the couple process-function (Y, u). The novelty with respect to classical McKean type equations consists in the form of the second equation, where, for each \(t>0\), in the classical case (\(\Lambda = 0\)) \(u(t,\cdot )\) was explicitely given by the marginal law of \(Y_t\). The present paper aims at proposing and implementing a stochastic particle algorithm to approximate (1.4) and investigating carefully its convergence properties.
(1.4) is the probabilistic representation of the partial integro-differential equation (PIDE)
in the sense that, given a solution (Y, u) of (1.4), there is a solution \({\bar{v}}\) of (1.5) in the sense of distributions, such that \(u=K*{\bar{v}}:=\int _{\mathbb R^d}K(\cdot -y){\bar{v}}(y)dy\). This follows, for instance, by a simple application of Itô’s formula, as explained in Theorems 6.1 and 6.2, Sect. 6 in [20]. Ideally our interest is devoted to (1.4) when the smoothing kernel K reduces to a Dirac measure at zero. To reach that scope, one would need to replace in previous equation K into \(K_\varepsilon ,\) where \(K_\varepsilon \) converges to the Dirac measure and to analyze the convergence of the corresponding solutions. However, such a theoretical analysis is out of the scope of this paper, but it will be investigated numerically via simulations reported at the end.
In fact, in the literature appear several probabilistic representations, with the objective of simulating numerically the corresponding PDE. One method which has been largely investigated for approximating solutions of time evolutionary PDEs is the method of forward-backward SDEs (FBSDEs). FBSDEs were initially developed in [23], see also [22] for a survey and [24] for a recent monograph on the subject. The idea is to express the PDE solution \(v(t,\cdot )\) at time t as the expectation of a functional of a so called forward diffusion process X, starting at time t. Based on that idea, many judicious numerical schemes have been proposed by [9, 14]. However, all those rely on computing recursively conditional expectation functions which is known to be a difficult task in high dimension. Besides, the FBSDE approach is blind in the sense that the forward process X is not ensured to explore the most relevant space regions to approximate efficiently the solution of the FBSDE of interest. On the theoretical side, the FBSDE representation of fully nonlinear PDEs still requires complex developments and is the subject of active research (see for instance [10]). Branching diffusion processes provide alternative probabilistic representation of semi-linear PDEs, involving a specific form of non-linearity on the zero order term. This type of approach has been recently extended in [15, 16] to a more general class of non-linearities on the zero order term, with the so-called marked branching process. One of the main advantages of this approach compared to FBSDEs is that it does not involve any regression computation to calculate conditional expectations. A third class of numerical approximation schemes relies on McKean type representations. In the time continuous framework, classical McKean representations are restricted to the conservative case (\(\Lambda =0\)). Relevant contributions at the algorithmic level are [4, 6–8], and the survey paper [28]. In the case \(\Lambda = 0\) with \(g=0\), but with \(\Phi \) possibly discontinuous, some empirical implementations were conducted in [2, 3] in the one-dimensional and multi-dimensional case respectively, in order to predict the large time qualitative behavior of the solution of the corresponding PDE.
In the present paper we extend this type of McKean based numerical schemes to the case of non-conservative PDEs (\(\Lambda \ne 0\)). An interesting aspect of this approach is that it is potentially able to represent fully nonlinear PDEs, by considering a more general class of functions \(\Lambda \) which may depend non-linearly not only on u but on its space derivatives up to the second order. This more general setting will be focused in a future work. In the discrete-time framework, Feynman-Kac formula and various types of related particle approximation schemes were extensively analyzed in the reference books of Del Moral [12] and [13] but without considering the specific case of a time continuous system (1.4) coupled with a weighting function \(\Lambda \) which depends nonlinearly on u.
By (3.3) we introduce an interacting particle system associated to (1.4). Indeed we replace one single McKean type stochastic differential equation with unknown process Y, with a system of N ordinary stochastic differential equations, whose solution consists in a system of particles \(\xi = (\xi ^{j,N})\), replacing the law of the process Y by the empirical mean law \(\displaystyle { S^N(\xi ):=\frac{1}{N} \sum _{j=1}^N\delta _{\xi ^{j,N}} }\).
In Theorem 4.2 we prove the convergence of the time-discretized particle system under Lipschitz type assumptions on the coefficients \(\Phi \), g and \(\Lambda \), obtaining an explicit rate. The mentioned rate is based on the contribution of two effects. First, the particle approximation error between the solution u of (1.4) and the approximation \(u^{S^N(\mathbf {\xi })}\), solution of
which is evaluated in Theorem 3.1. The second effect is the time discretization error, established in Proposition 4.1. The errors are evaluated in the \(L^p, p = 2, +\infty \) mean distance, in terms of the number N of particles and the time discretization step. One significant consequence of Theorem 3.1 is Corollary 3.2 which states the chaos propagation of the interacting particle system.
We emphasize that the proof of Theorem 3.1 relies on Proposition 3.3, whose formula (3.12) allows to control the particle approximation error without use of exchangeability assumptions on the particle system, see Remark 3.4.
The paper is organized as follows. After this introduction, we formulate the basic assumptions valid along the paper and recall important results proved in [20] and used in the sequel. The evaluation of the particle approximation error is discussed in Sect.3. Section 4 focuses on the convergence of the time-discretized particle system. Finally in Sect .5 we provide numerical simulations illustrating the performances of the interacting particle system in approximating the limit PDE (i.e. when the smoothing kernel K reduces to a Dirac measure at zero), in a specific case where the solution is explicitely known.
2 Notations and assumptions
Let us consider \(\mathcal {C}^d:={\mathcal {C}}([0,T],\mathbb R^d)\) metrized by the supremum norm \(\Vert \cdot \Vert _{\infty }\), equipped with its Borel \(\sigma -\) field \({\mathcal {B}}(\mathcal {C}^d) = \sigma (X_t,t \ge 0)\) (and \({\mathcal {B}}_t(\mathcal {C}^d) := \sigma (X_u,0 \le u \le t)\) the canonical filtration) and endowed with the topology of uniform convergence. X will be the canonical process on \(\mathcal {C}^d\) and \({\mathcal {P}}_r(\mathcal {C}^d)\) the set of Borel probability measures on \(\mathcal {C}^d\) admitting a moment of order \(r \ge 0\). For \(r=0\), \({\mathcal {P}}(\mathcal {C}^d) := {\mathcal {P}}_0(\mathcal {C}^d)\) is naturally the Polish space (with respect to the weak convergence topology) of Borel probability measures on \(\mathcal {C}^d\) naturally equipped with its Borel \(\sigma \)-field \({\mathcal {B}}(\mathcal {P}(\mathcal {C}^d))\). When \(d=1\), we often omit it and we simply set \({\mathcal {C}} := {\mathcal {C}}^1\).
We recall that the Wasserstein distance of order r and respectively the modified Wasserstein distance of order r for \(r \ge 1\), between m and \(m'\) in \({\mathcal {P}}_r({\mathcal {C}}^d) \), denoted by \(W^r_{T}(m,m')\) (and resp. \(\widetilde{W}^r_{T}(m,m')\)) are such that
where \(\Pi (m,m')\) (resp. \(\widetilde{\Pi }(m,m')\)) denotes the set of Borel probability measures in \(\mathcal {P}(\mathcal {C}^d \times \mathcal {C}^d)\) with fixed marginals m and \(m'\) belonging to \(\mathcal {P}_r(\mathcal {C}^d)\) (resp. \(\mathcal {P}(\mathcal {C}^d)\) ). In this paper we will use very frequently the Wasserstein distances of order 2. For that reason, we will simply set \(W_t: = W^2_t\) (resp. \({\tilde{W}}_t: = {\tilde{W}}^2_t\)).
Given \(N \in \mathbb N^{\star }\), \(l \in \mathcal {C}^d\), \(l^1, \ldots , l^N \in \mathcal {C}^d\), a significant role in this paper will be played by the Borel measures on \(\mathcal {C}^d\) given by \(\delta _l\) and \(\displaystyle { \frac{1}{N} \sum _{j=1}^N \delta _{l^j}}\).
Remark 2.1
Given \(l^1,\ldots ,l^N, \tilde{l}^1,\ldots , \tilde{l}^N \in \mathcal {C}^{d}\), by definition of the Wasserstein distance we have, for all \(t \in [0,T]\)
In this paper \(\mathcal {C}_b(\mathcal {C}^d)\) denotes the space of bounded, continuous real-valued functions on \(\mathcal {C}^d\), for which the supremum norm is denoted by \(\Vert \cdot \Vert _{\infty }\). \(\mathbb R^d\) is equipped with the scalar product \(\cdot \) and \(\vert x\vert \) stands for the induced Euclidean norm for \(x \in \mathbb R^d\). Given two reals a, b (\(d=1\)) we will denote in the sequel \(a \wedge b := \min (a,b)\) and \(a \vee b := \max (a,b)\).
\(\mathcal {M}_f(\mathbb R^d)\) is the space of finite, Borel measures on \(\mathbb R^d\). \(\mathcal {S}(\mathbb R^d)\) is the space of Schwartz fast decreasing test functions and \(\mathcal {S}'(\mathbb R^d)\) is its dual. \({\mathcal {C}}_b(\mathbb R^d)\) is the space of bounded, continuous functions on \(\mathbb R^d\), \({\mathcal {C}}^{\infty }_0(\mathbb R^d)\) is the space of smooth functions with compact support. \({\mathcal {C}}^{\infty }_b(\mathbb R^d)\) is the space of bounded and smooth functions. \({\mathcal {C}}_0(\mathbb R^d)\) represents the space of continuous functions with compact support in \(\mathbb R^d\). \(W^{r,p}(\mathbb R^d)\) is the Sobolev space of order \(r \in \mathbb N\) in \((L^p(\mathbb R^d),||\cdot ||_{p})\), with \(1 \le p \le \infty \).
\({\mathcal {F}}(\cdot ): f \in \mathcal {S}(\mathbb R^d) \mapsto {\mathcal {F}}(f) \in \mathcal {S}(\mathbb R^d)\) will denote the Fourier transform on the classical Schwartz space \(\mathcal {S}(\mathbb R^d)\) such that for all \(\xi \in \mathbb R^d\),
We will designate in the same manner the corresponding Fourier transform on \(\mathcal {S}'(\mathbb R^d)\).
For any Polish space E, we will designate by \(\mathcal {B}(E)\) its Borel \(\sigma \)-field. It is well-known that \(\mathcal {P}(E)\) is also a Polish space with respect to the weak convergence topology, whose Borel \(\sigma \)-field will be denoted by \(\mathcal {B}(\mathcal {P}(E))\) (see Proposition 7.20 and Proposition 7.23, Sect. 7.4 Chapter 7 in [5]).
Let \((\Omega ,\mathcal {F})\) be a measured space. A map \(\eta : (\Omega ,\mathcal {F}) \longrightarrow (\mathcal {P}(E),\mathcal {B}(\mathcal {P}(E)))\) will be called random probability (or random probability kernel) if it is measurable. We will indicate by \(\mathcal {P}^{\Omega }(E)\) the space of random probabilities.
Remark 2.2
Let \(\eta : (\Omega ,\mathcal {F}) \longrightarrow (\mathcal {P}(E),\mathcal {B}(\mathcal {P}(E)))\). \(\eta \) is a random probability if and only if the two following conditions hold:
-
for each \(\bar{\omega } \in \Omega \), \(\eta _{\bar{\omega }} \in \mathcal {P}(E)\),
-
for all Borel set \(A \in \mathcal {B}(\mathcal {P}(E))\), \(\bar{\omega } \mapsto \eta _{\bar{\omega }}(A)\) is \(\mathcal {F}\)-measurable.
This was highlighted in Remark 3.20 in [11] (see also Proposition 7.25 in [5]).
Remark 2.3
Given \(\mathbb R^d\)-valued continuous processes \(Y^1,\ldots , Y^n\), the application \(\displaystyle { \frac{1}{N} \sum _{j=1}^N \delta _{Y^j} }\) is a random probability on \(\mathcal {P}(\mathcal {C}^d)\). In fact \(\delta _{Y^j}, 1 \le j \le N\) is a random probability by Remark 2.2.
In this article, the following assumptions will be used.
Assumption 1
-
1.
\(\Phi \) and g are Borel functions defined on \([0,T] \times \mathbb R^d \times \mathbb R\) taking values respectively in \(\mathbb R^{d\times p}\) (space of \(d \times p\) matrices) and \(\mathbb R^d\) that are Lipschitz w.r.t. space variables: there exist finite positive reals \(L_\Phi \) and \(L_g\) such that for any \((t,y,y',z,z')\in [0,T] \times \mathbb R^d \times \mathbb R^d \times \mathbb R\times \mathbb R\), we have
$$\begin{aligned}&\vert \Phi (t,y',z')-\Phi (t,y,z)\vert \le L_\Phi (\vert z'-z\vert + \vert y'-y\vert ) \quad \text {and}\\&\quad \vert g(t,y',z')-g(t,y,z)\vert \le L_g (\vert z'-z\vert + \vert y'-y\vert )\ . \end{aligned}$$ -
2.
\(\Lambda \) is a Borel real valued function defined on \([0,T]\times \mathbb R^{d} \times \mathbb R\) Lipschitz w.r.t. the space variables: there exists a finite positive real, \(L_{\Lambda }\) such that for any \((t,y,y',z,z')\in [0,T] \times \mathbb R^d\times \mathbb R^d\times \mathbb R\times \mathbb R\), we have
$$\begin{aligned} \vert \Lambda (t,y,z)-\Lambda (t,y',z')\vert \le L_{\Lambda } (\vert y'-y\vert +\vert z'-z\vert )\ . \end{aligned}$$ -
3.
\(\Lambda \) is supposed to be uniformly bounded: there exist a finite positive real \(M_\Lambda \) such that, for any \((t,y,z)\in [0,T] \times \mathbb R^d \times \mathbb R\)
$$\begin{aligned} \vert \Lambda (t,y,z)\vert \le M_\Lambda \ . \end{aligned}$$ -
4.
\(K : \mathbb R^d \rightarrow \mathbb R_+\) is integrable, Lipschitz, bounded and with integral equal to 1: there exist finite positive reals \(M_K\) and \(L_K\) such that for any \((y,y')\in \mathbb R^d\times \mathbb R^d\)
$$\begin{aligned} \vert K(y) \vert \le M_K, \quad \vert K(y')-K(y)\vert \le L_K \vert y'-y\vert \ \quad \text {and} \quad \int _{\mathbb R^d} K(x) dx = 1 \ . \end{aligned}$$ -
5.
\(\zeta _0\) is a fixed Borel probability measure on \(\mathbb R^d\) admitting a second order moment.
-
6.
The functions \(s \in [0,T] \mapsto \Phi (s,0,0)\) and \(s \in [0,T] \mapsto g(s,0,0)\) are bounded. \(m_{\Phi }\) (resp. \(m_g\)) will denote the supremum \(\sup _{s \in [0,T]} \vert \Phi (s,0,0) \vert \) (resp. \(\sup _{s \in [0,T]} \vert g(s,0,0) \vert \)).
Given a finite signed Borel measure \(\gamma \) on \(\mathbb R^d\), \(K * \gamma \) will denote the convolution function \(x \mapsto \gamma (K(x - \cdot ))\). In particular if \(\gamma \) is absolutely continuous with density \({\dot{\gamma }}\), then \((K * \gamma )(x) = \int _{\mathbb R^d} K(x-y) \dot{\gamma }(y)dy\).
To simplify we introduce the following notations.
-
\(V\,:[0,T] \times {\mathcal C}^d \times {\mathcal {C}}\rightarrow \mathbb R\) defined for any pair of functions \(y\in {\mathcal {C}}^d\) and \(z\in {\mathcal {C}}\), by
$$\begin{aligned} V_t(y,z):=\exp \left( \int _0^t \Lambda (s,y_s,z_s) ds\right) \quad \text {for any} \ t\in [0,T]\ . \end{aligned}$$(2.3) -
The real valued process Z such that \(Z_s=u(s,Y_s)\), for any \(s\in [0,T]\), will often be denoted by u(Y).
With these new notations, the second equation in (1.4) can be rewritten as
where \(u(t,\cdot )=\frac{d\nu _t}{dx}\) and \(\check{K}(x) := K(-x)\).
Remark 2.4
Under Assumption 1. 3(b), \(\Lambda \) is bounded. Consequently
Under Assumption 1. 2. \(\Lambda \) is Lipschitz. Then V inherits in some sense this property. Indeed, observe that for any \((a,b)\in \mathbb R^2\),
Then for any continuous functions \(y,\,y'\in {\mathcal {C}}^d ={\mathcal {C}}([0,T],\mathbb R^d)\), and \(z,\,z'\in {\mathcal {C}}([0,T],\mathbb R)\), taking \(a=\int _0^t\Lambda (s,y_s,z_s)ds\) and \(b=\int _0^{t}\Lambda (s,y'_s,z'_s)ds\) in the above equality yields
In Sect.4, Assumption 1. will be replaced by what follows.
Assumption 2
All items of Assumption 1. are in force excepted 1 and 2 which are replaced by the following.
-
1.
There exist positive reals \(L_{\Phi }\), \(L_g\) such that, for any \((t,t',y,y',z,z')\in [0,T]^2\times (\mathbb R^d)^2\times \mathbb R^2\),
$$\begin{aligned}&\vert \Phi (t,y,z)-\Phi (t',y',z')\vert \le L_{\Phi }\,( \vert t-t'\vert ^{\frac{1}{2}}+\vert y-y'\vert +\vert z-z'\vert ), \\&\vert g (t,y,z)-g (t',y',z')\vert \le L_{g}\,( \vert t-t'\vert ^{\frac{1}{2}}+\vert y-y'\vert +\vert z-z'\vert ) . \end{aligned}$$ -
2.
There exists a positive real \(L_{\Lambda }\) such that, for any \((t,t',y,y',z,z')\in [0,T]^2\times (\mathbb R^d)^2\times \mathbb R^2\),
$$\begin{aligned} \vert \Lambda (t,y,z)-\Lambda (t',y',z')\vert \le L_{\Lambda }\,( \vert t-t'\vert ^{\frac{1}{2}}+\vert y-y'\vert +\vert z-z'\vert ). \end{aligned}$$
We end this section by recalling important results established in our companion paper [20], for which Assumption 1. is supposed to be satisfied. Let us first remark that the second equation of (1.4) can be rewritten as
with \(m = m_Y\) being the law of the process Y on the canonical space \(\mathcal {C}^d\).
Indeed for every \(m \in \mathcal {P}(\mathcal {C}^d)\), Theorem 3.1 of [20] shows that Eq. (2.8) is well-posed and so it properly defines a function \(u^m\). The lemma below, established in Proposition 3.3 of [20], states stability results on the function \((m,t,y) \mapsto u^m(t,y)\).
Proposition 2.5
We assume the validity of items 2, 3 and 4 of Assumption 1.
The following assertions hold.
-
1.
For any couple of probabilities \((m,m')\in {\mathcal {P}}_2({\mathcal {C}}^d)\times {\mathcal {P}}_2({\mathcal {C}}^d)\), for all \((t,y,y') \in [0,T] \times \mathcal {C}^d \times \mathcal {C}^d\), we have
$$\begin{aligned} \vert u^m\big (t,y\big )-u^{m'}\big (t,y'\big )\vert ^2\le C_{K,\Lambda }(t)\left[ \vert y-y'\vert ^2+\vert W_t(m,m')\vert ^2\right] \ , \end{aligned}$$(2.9)where \(C_{K,\Lambda }(t):=2C'_{K,\Lambda }(t)(t+2)(1+e^{2tC'_{K,\Lambda }(t)})\) with \(C'_{K,\Lambda }(t)=2e^{2tM_{\Lambda }}(L^2_K+2M^2_KL^2_\Lambda t )\). In particular the function \(C_{K,\Lambda }\) only depends on \(M_K, L_K, M_\Lambda , L_\Lambda \) and t and is increasing with t.
-
2.
For any \((m,m') \in \mathcal {P}(C^d) \times \mathcal {P}(C^d)\), for all \((t,y,y') \in [0,T] \times \mathcal {C}^d \times \mathcal {C}^d\), we have
$$\begin{aligned} \vert u^m\big (t,y\big )-u^{m'}\big (t,y'\big )\vert ^2\le \mathfrak {C}_{K,\Lambda }(t)\left[ \vert y-y'\vert ^2+\vert \widetilde{W}_t(m,m')\vert ^2\right] \ , \end{aligned}$$(2.10)where \(\mathfrak {C}_{K,\Lambda }(t) := 2e^{2tM_{\Lambda }}(\max (L_K,2M_K)^2 + 2M_{K}^2\max (L_{\Lambda },2M_{\Lambda })^2 t ) \).
-
3.
The function \( (m,t,x) \mapsto u^m(t,x)\) is continuous on \(\mathcal {P}(\mathcal {C}^d) \times [0,T] \times \mathbb R^d,\) where \(\mathcal {P}(\mathcal {C}^d)\) is endowed with the topology of weak convergence.
-
4.
Suppose that \(K \in W^{1,2}(\mathbb R^d)\). Then for any \((m,m')\in {\mathcal {P}}_2({\mathcal {C}}^d)\times {\mathcal {P}}_2({\mathcal {C}}^d)\), \(t \in [0,T]\)
$$\begin{aligned} \Vert u^m(t,\cdot )-u^{m'}(t,\cdot )\Vert _2^2 \le \tilde{C}_{K,\Lambda }(t)(1+2tC_{K,\Lambda }(t)) \vert W_t(m,m') \vert ^2 \ ,\quad \end{aligned}$$(2.11)where \(C_{K,\Lambda }(t):=2C'_{K,\Lambda }(t)(t+2)(1+e^{2tC'_{K,\Lambda }(t)})\) with \(C'_{K,\Lambda }(t)=2e^{2tM_{\Lambda }}(L^2_K+2M^2_KL^2_\Lambda t )\) and \(\tilde{C}_{K,\Lambda }(t) := 2 e^{2tM_{\Lambda }}(2M_K L_{\Lambda }^2 t(t+1) + \Vert \nabla K \Vert _2^2 )\), \(\Vert \cdot \Vert _2\) being the standard \(L^2(\mathbb R^d)\) or \(L^2(\mathbb R^d,\mathbb R^d)\)-norms. In particular the functions \( t \mapsto C'_{K, \Lambda }(t)\) and \( t \mapsto C_{K, \Lambda }(t)\) only depend on \(M_K, L_K, M_\Lambda , L_\Lambda \) and are increasing with respect to t.
-
5.
Suppose that \(\mathcal {F}(K) \in L^1(\mathbb R^d)\). Then there exists a constant \({\bar{C}}_{K,\Lambda }(t) > 0\) (depending only on \(t,M_{\Lambda },L_{\Lambda },\Vert \mathcal {F}(K) \Vert _1\)) such that for any random probability \(\eta : (\Omega ,\mathcal {F}) \longrightarrow (\mathcal {P}_2(\mathcal {C}^d),\mathcal {B}(\mathcal {P}(\mathcal {C}^d)))\), for all \((t,m) \in [0,T] \times \mathcal {P}(\mathcal {C}^d)\)
$$\begin{aligned} \mathbb E{ [ \Vert u^{\eta }(t,\cdot ) - u^m(t,\cdot ) \Vert _{\infty }^2 ] }\le & {} {\bar{C}}_{K,\Lambda }(t) \sup _{ \underset{\Vert \varphi \Vert _{\infty } \le 1}{\varphi \in \mathcal {C}_b(\mathcal {C}^d)}} \mathbb E{ [ \vert \langle \eta - m , \varphi \rangle \vert ^2 ]} \ ,\quad \end{aligned}$$(2.12)where we recall that \(\mathcal {P}(\mathcal {C}^d)\) is endowed with the topology of weak convergence. We remark that the expectation in both sides of (2.12) is taken w.r.t. the randomness of the random probability \(\eta \).
Remark 2.6
The map \(\displaystyle { d_2^{\Omega } : (\nu ,\mu ) \mapsto \sqrt{\sup _{ \underset{\Vert \varphi \Vert _{\infty } \le 1}{\varphi \in \mathcal {C}_b(\mathcal {C}^d)}} \mathbb E[ \vert \langle \nu - \mu , \varphi \rangle \vert ^2 ] } }\) defines a (homogeneous) distance on \(\mathcal {P}^{\Omega }(\mathcal {C}^d)\).
The lemma below was proved in Lemma 7.1 in [20].
Lemma 2.7
Let \(r:\,[0,T]\mapsto [0,T]\) be a non-decreasing function such that \(r(s)\le s\) for any \(s\in [0,T]\) and \(Y_0\) be a random variable admitting \(\zeta _0\) as law.
Let \(\mathcal {U}: (t,y) \in [0,T] \times \mathcal {C}^d \rightarrow \mathbb R\) (respectively \(\mathcal {U}' : (t,y) \in [0,T] \times \mathcal {C}^d \rightarrow \mathbb R\)), be a given Borel function such that for all \(t \in [0,T]\), there is a Borel map \(\mathcal {U}_t: \mathcal {C}([0,t],\mathbb R^d) \rightarrow \mathbb R\) (resp. \(\mathcal {U}^{'}_t: \mathcal {C}([0,t],\mathbb R^d) \rightarrow \mathbb R\)) such that \(\mathcal {U}(t,\cdot ) = \mathcal {U}_t(\cdot )\) (resp. \(\mathcal {U}'(t,\cdot ) = \mathcal {U}'_t(\cdot )\)).
Then the following two assertions hold.
-
1.
Consider Y (resp. \(Y'\)) a solution of the following SDE for \(v=\mathcal {U}\) (resp. \(v=\mathcal {U}'\)):
$$\begin{aligned} Y_t= & {} Y_0+\int _0^t\Phi (r(s),Y_{r(s)},v(r(s),Y_{\cdot \wedge r(s)}))dW_s+\int _0^t g(r(s),Y_{r(s)},v(r(s),Y_{\cdot \wedge r(s)}))ds\ ,\nonumber \\&\text {for any}\ t\in [0,T] \ , \end{aligned}$$(2.13)where, we emphasize that for all \(\theta \in [0,T]\), \(Z_{\cdot \wedge \theta } := \{Z_u, 0 \le u \le \theta \} \in \mathcal {C}([0,\theta ],\mathbb R^d)\) for any continuous process Z. For any \( a \in [0,T]\), we have
$$\begin{aligned} \mathbb E[\sup _{t\le a} \vert Y'_t-Y_t\vert ^2] \le C_{\Phi ,g}(T)\mathbb E\left[ \int _0^a \vert \mathcal {U}(r(t),Y_{\cdot \wedge r(t)})-\mathcal {U}'(r(t),Y'_{\cdot \wedge r(t)}) \vert ^2dt \right] \ , \end{aligned}$$(2.14)where \(C_{\Phi ,g}(T)=12(4L^2_{\Phi }+TL^2_g)e^{12T(4L^2_{\Phi }+TL^2_g)}\).
-
2.
Suppose moreover that \(\Phi \) and g are \(\frac{1}{2}\)-Hölder w.r.t. the time and Lipschitz w.r.t. the space variables i.e. there exist some positive constants \(L_{\Phi }\) and \(L_g\) such that for any \((t,t',y,'y',z,z')\in [0,T]^2\times \mathbb R^{2d}\times \mathbb R^2\)
$$\begin{aligned} \left\{ \begin{array}{l} \vert \Phi (t,y,z)-\Phi (t',y',z')\vert \le L_{\Phi } (\vert t-t'\vert ^{\frac{1}{2}} +\vert y-y'\vert +\vert z-z'\vert )\\ \vert g(t,y,z)-g(t',y',z')\vert \le L_{g} (\vert t-t'\vert ^{\frac{1}{2}} +\vert y-y'\vert +\vert z-z'\vert )\ . \end{array} \right. \end{aligned}$$(2.15)Let \(r_1, r_2:\,[0,T]\mapsto [0,T]\) being two non-decreasing functions verifying \(r_1(s)\le s\) and \(r_2(s)\le s\) for any \(s\in [0,T]\). Let Y (resp. \(Y'\)) be a solution of (2.13) for \(v=\mathcal {U}\) and \(r=r_1\) (resp. \(v=\mathcal {U}'\) and \(r=r_2\)). Then for any \( a \in [0,T]\), the following inequality holds:
$$\begin{aligned} \mathbb E[\sup _{t\le a} \vert Y'_t-Y_t\vert ^2]\le & {} C_{\Phi ,g}(T)\left( \Vert r_1-r_2\Vert _{L^1([0,T])} +\int _0^a\mathbb E[\vert Y'_{r_1(t)}-Y'_{r_2(t)}\vert ^2] dt\right. \nonumber \\&\left. +\,\mathbb E\left[ \int _0^a\vert \mathcal {U}(r_1(t),Y_{\cdot \wedge r_1(t)})-\mathcal {U}'(r_2(t),Y'_{\cdot \wedge r_2(t)})\vert ^2dt\right] \right) ,\nonumber \\ \end{aligned}$$(2.16)
The theorem below was the object of Theorem 3.9 in [20].
Theorem 2.8
Under Assumption 1, the McKean type SDE (1.4) admits strong existence and pathwise uniqueness.
For a precise formulation of the notion of existence and uniqueness for the McKean type equation (1.4) we refer to Definition 2.6 of [20].
We finally recall an important non-anticipating property of the map \((m,t,x) \mapsto u^m(t,x)\), stated in [20].
Definition 2.9
Let us fix \(t \in [0,T]\). Given a non-negative Borel measure m on \(({\mathcal {C}}^d,\mathcal {B}(\mathcal {C}^d))\). From now on, \(m_t\) will denote the (unique) induced measure on \(({\mathcal {C}}_t^d,\mathcal {B}(\mathcal {C}^d_t))\) (with \({\mathcal {C}}_t^d := {\mathcal {C}}([0,t],\mathbb R^d)\)) defined by
where \(F : {\mathcal {C}}_t^d \longrightarrow \mathbb R\) is bounded and continuous.
Remark 2.10
Let \(t \in [0,T], m = \delta _{\xi } \;, \xi \in {\mathcal {C}}^d\). The induced measure \(m_t\), on \(\mathcal {C}_t^d\), is \(\delta _{(\xi _r | 0 \le r \le t)} \).
For each \(t \in [0,T]\), the same construction as the one carried on in Theorem 3.1 in [20] allows us to define the unique solution to
The proposition and corollary below were the object of Proposition 3.7 and Corollary 3.8 in [20].
Proposition 2.11
Under Assumption 1, we have
Corollary 2.12
Let \(N \in \mathbb N\), \(\xi ^1, \ldots , \xi ^i, \ldots , \xi ^N\) be \((\mathcal {G}_t)\)-adapted continuous processes, where \(\mathcal {G}\) is a filtration (defined on some probability space) fulfilling the usual conditions. Let \(m(d\omega ) = \frac{1}{N} \sum _{i=1}^{N} \delta _{\xi ^i}(d\omega )\). Then, \((u^m(t,y))\) is a \((\mathcal {G}_t)\)-adapted random field, i.e. for any \((t,y) \in [0,T] \times \mathbb R^d\), the process is \((\mathcal {G}_t)\)-adapted.
3 Particle systems approximation and propagation of chaos
In this section, we introduce an interacting particle system \(\xi = (\xi ^{i,N})_{i=1, \ldots , N}\) whose empirical law will be shown to converge to the law of the solution Y of the McKean type equation (1.4). This is a consequence of the so called propagation of chaos which describes the asymptotic independence of the components of \(\xi \) when the size N of the particle system goes to \(\infty \). That property was introduced in [21] and further developed and popularized by [27]. The convergence of \((\xi ^{i,N})_{i=1, \ldots , N}\) induces a natural approximation of u, solution of (1.4).
We suppose here the validity of Assumption 1. Let \((\Omega , \mathcal F, \mathbb P)\) be a fixed probability space, and \((W^i)_{i=1, \ldots ,N}\) be a sequence of independent \(\mathbb R^p\)-valued Brownian motions. Let \((Y_0^i)_{i=1, \ldots ,N}\) be i.i.d. r.v. according to \(\zeta _0\). We consider \(\mathbf {Y}:=(Y^i)_{i=1, \ldots ,N}\) the sequence of processes such that \((Y^i, u^{m^i})\) are solutions to
recalling that \(V_t\big (Y^i,u^{m^i}(Y^i)\big )=\exp \big ( \int _0^t\Lambda _s(Y^i_s,u^{m^i}_s(Y^i_s))ds \big )\). The existence and uniqueness of the solution of each equation is ensured by Theorem 2.8. We recall that the map \((m,t,y) \mapsto u^m(t,y)\) fulfills the regularity properties given at the second and third item of Proposition 2.5 .
Obviously the processes \((Y^i)_{i=1, \ldots ,N}\) are independent. They are also identically distributed since Theorem 2.8 also states uniqueness in law.
So we can define \(m^0:=m^i\) the common distribution of the processes \(Y^i, i=1, \ldots ,N\), which is of course the law of the process Y, such that (Y, u) is a solution of (1.4).
From now on, \({\mathcal C}^{dN}\) will denote \(( {\mathcal C}^{d})^N\), which is obviously isomorphic to \(\mathcal {C}([0,T], \mathbb R^{dN})\). For every \({\bar{\xi }} \in {\mathcal C}^{dN}\) we will denote
The function \((t,x) \mapsto u^{S^N({\bar{\mathbf {\xi }}})}_t(x)\) is obtained by composition of \(m \mapsto u^m_t(x)\) (defined in (2.8)) with \( m = S^N({\bar{\mathbf {\xi }}})\).
Now let us introduce the system of equations
Conformally with (3.2), we consider the empirical (random) measure \(\displaystyle { S^N(\mathbf {Y})=\frac{1}{N} \sum _{i=1}^N} \delta _{Y^{i}} \) related to \(\mathbf{Y} := (Y^i)_{i=1, \ldots ,N},\) where we recall that for each \(i \in \{1, \ldots ,N\}\), \(Y^i\) is solution of (3.1). We observe that by Remark 2.3, \(S^N(\mathbf {\xi })\) and \(S^N(\mathbf {Y})\) are measurable maps from \((\Omega ,\mathcal {F})\) to \((\mathcal {P}(\mathcal {C}^d),\mathcal {B}(\mathcal {P}(\mathcal {C}^d)))\); moreover \(S^N(\xi ),S^N({\mathbf{Y}}) \in \mathcal {P}_2(\mathcal {C}^d)\) \(\mathbb P\)-a.s. A solution \(\mathbf{{\xi }}:=(\xi ^{i,N})_{i=1, \ldots ,N}\) of (3.3) is called interacting particle system.
The first line of (3.3) is in fact a path-dependent stochastic differential equation. We claim that its coefficients are measurable. Indeed, the map \((t,\bar{\xi }) \mapsto (S^{N}(\bar{\xi }),t,\bar{\xi }_t^i,)\) being continuous from \(([0,T] \times \mathcal {C}^{dN},\mathcal {B}([0,T]) \otimes \mathcal {B}(\mathcal {C}^{dN}))\) to \(( \mathcal {P}(\mathcal {C}^{d}) \times [0,T] \times \mathbb R^d , \mathcal {B}(\mathcal {P}(\mathcal {C}^d)) \otimes \mathcal {B}([0,T]) \otimes \mathcal {B}(\mathbb R^d)) \) for all \(i \in \{1, \ldots ,N\}\), by composition with the continuous map \((m,t,y) \mapsto u^m(t,y)\) (see Proposition 2.5 3.) we deduce the continuity of \((t,\bar{\xi }) \mapsto (u_t^{S^N(\bar{\xi })}(\bar{\xi }^i_t))_{i=1, \ldots ,N}\), and so the measurability from \(([0,T] \times \mathcal {C}^{dN},\mathcal {B}([0,T]) \otimes \mathcal {B}(\mathcal {C}^{dN}))\) to \((\mathbb R,\mathcal {B}(\mathbb R))\).
In the sequel, for simplicity we set \(\bar{\xi }_{r \le s}:= (\bar{\xi }^i_{r \le s})_{1 \le i \le N}\). We remark that, by Proposition 2.11 and Remark 2.10, we have
for any \(s \in [0,T], \; \bar{\xi } \in {\mathcal C}^{dN}\) and so stochastic integrands of (3.3) are adapted (so progressively measurable being continuous in time) and so the corresponding Itô integral makes sense. We discuss below the well-posedness of (3.3).
The fact that (3.3) has a unique (strong) solution \((\xi ^{i,N})_{i=1, \ldots N}\) holds true because of the following arguments.
-
1.
\(\Phi \) and g are Lipschitz. Moreover the map \({\bar{\mathbf {\xi }}}_{r\le s} \mapsto \left( u^{S^N({\bar{\mathbf {\xi }}_{r \le s} })}_s(\bar{\xi }^{i}_s) \right) _{i=1, \ldots ,N}\) is Lipschitz. Indeed, for given \((\xi _{r \le s},\eta _{r \le s}) \in \mathcal {C}^{dN} \times \mathcal {C}^{dN} \), \(s \in [0,T]\), by using successively inequality (2.9) of Proposition 2.5 and Remark 2.1, for all \(i \in \{1, \ldots ,N\}\) we have
$$\begin{aligned} \vert u_s^{S^N(\xi _{r \le s})}(\xi ^i_{t}) - u_s^{S^N(\eta _{r \le s})}(\eta ^i_{t}) \vert\le & {} \sqrt{C_{K,\Lambda }(T)} \left( \vert \xi ^i_s - \eta _s^i \vert + \frac{1}{N} \sum _{j=1}^N \sup _{0 \le r \le s}\vert \xi ^j_r- \eta ^j_r \vert \right) \nonumber \\\le & {} 2\sqrt{C_{K,\Lambda }(T)} \max _{j=1, \ldots ,N} \sup _{0 \le r \le s}\vert \xi ^j_r-\eta ^j_r \vert \ . \end{aligned}$$(3.5)Finally the functions
$$\begin{aligned} {\bar{\mathbf {\xi }}}_{r\le s}\mapsto & {} \left( \Phi (s, \bar{\xi }^i_s,u_s^{S^N({\bar{\mathbf {\xi }}}_r, r \le s)} (\bar{\xi }^{i}_s))\right) _{i=1, \ldots N} \\ {\bar{\mathbf {\xi }}}_{r\le s}\mapsto & {} \left( g(s, \bar{\xi }^i_s, u_s^{S^N ({\bar{\mathbf {\xi }}}_r, r \le s)} (\bar{\xi }^{i}_s))\right) _{i=1, \ldots N} \end{aligned}$$are uniformly Lipschitz and bounded.
-
2.
A classical argument of well-posedness for systems of path-dependent stochastic differential equations with Lipschitz dependence on the sup-norm of the path, see Chapter V, Sect. 2.11, Theorem 11.2 page 128 in [25].
After the preceding introductory considerations, we can state and prove the main theorem of the section.
Theorem 3.1
Let us suppose the validity of Assumption 1. Let N be a fixed positive integer. Let \((Y^i)_{i=1, \ldots ,N}\) (resp. (\((\xi ^{i,N})_{i=1, \ldots ,N}\)) be the solution of (3.1) (resp. (3.3)), let \(m^0\) as defined after (3.1). The following assertions hold.
-
1.
If \(\mathcal {F}(K) \in L^1(\mathbb R^d)\), there is a positive constant C only depending on \(L_\Phi , L_g,M_K,M_{\Lambda },L_K,L_{\Lambda },T, \Vert \mathcal {F}(K) \Vert _1 \), such that, for all \(i=1, \ldots ,N\) and \(t \in [0,T]\),
$$\begin{aligned} \mathbb E\Big [ \Big \Vert u_t^{S^N(\xi )}-u^{m^0}_t\Big \Vert _{\infty }^2\Big ]\le & {} \frac{C}{N} \end{aligned}$$(3.6)$$\begin{aligned} \mathbb E\left[ \sup _{0 \le s\le t} \vert \xi ^{i,N}_s-Y^i_s\vert ^2\right]\le & {} \frac{C}{N}\ . \end{aligned}$$(3.7) -
2.
If K belongs to \(W^{1,2}(\mathbb R^d)\), there is a positive constant C only depending on \(L_\Phi , L_g, M_K,M_{\Lambda },L_K,L_{\Lambda },T\) and \(\Vert \nabla K\Vert _2\), such that, for all \(t \in [0,T]\),
$$\begin{aligned} \mathbb E\left[ \Big \Vert u_t^{S^N(\xi )}-u^{m^0}_t\Big \Vert _{2} ^2\right]\le & {} \frac{C}{N} \ . \end{aligned}$$(3.8)
Before proving Theorem 3.1, we remark that the propagation of chaos follows easily.
Corollary 3.2
Under Assumption 1, the propagation of chaos holds for the interacting particle system \((\xi ^{i,N})_{i \in \mathbb N}\).
Proof
We prove here that Theorem 3.1 implies the propagation of chaos.
Indeed, for all \(k \in \mathbb N^{\star }\), (3.7) implies
which implies in particular the convergence in law of the vector \((\xi ^{1,N},\xi ^{2,N}, \ldots ,\xi ^{k,N})\) to \((Y^1,Y^2, \ldots ,Y^k)\). Consequently, since \(({Y}^{i})_{i=1, \ldots ,k}\) are i.i.d. according to \(m^0\)
\(\square \)
The validity of (3.6) and (3.7) will be the consequence of the significant more general proposition below.
Proposition 3.3
Let us suppose the validity of Assumption 1. Let N be a fixed positive integer. Let \((W^{i,N})_{i=1, \ldots ,N}\) be a family of p-dimensional standard Brownian motions (not necessarily independent). Let \(({Y}^i_0)_{i=1, \ldots ,N}\) be the family of i.i.d. r.v. initializing the system (3.1). We consider the processes \((\bar{Y}^{i,N})_{i=1, \ldots ,N}\), such that for each \(i \in \{1, \ldots ,N\}\), \(\bar{Y}^{i,N}\) is the unique strong solution of
recalling that \(V_t\big (Y^{i,N},u^{m^{i,N}}(Y^{i,N})\big )= \exp \big ( \int _0^t\Lambda (s,Y^{i,N}_s,u^{m^{i,N}}_s(Y^{i,N}_s))ds \big )\).
Let us consider now the system of equations (3.3), where the processes \(W^i\) are replaced by \(W^{i,N}\), i.e.
Then the following assertions hold.
-
1.
For any \(i=1, \ldots N\), \((\bar{Y}^{i,N}_t)_{t\in [0,T]}\) have the same law \(m^{i,N}=m^0\), where \(m^0\) is the common law of processes \((Y^i)_{i=1, \ldots ,N}\) defined by the system (3.1).
-
2.
Equation (3.11) admits a unique strong solution.
-
3.
Suppose moreover that \(\mathcal {F}(K)\) is in \(L^1(\mathbb R^d)\). Then there is a positive constant C only depending on \(L_\Phi , L_g,M_K,M_{\Lambda },L_K,L_{\Lambda },T\) and \( \Vert \mathcal {F}(K) \Vert _1 \) such that, for all \(t \in [0,T]\),
$$\begin{aligned}&\sup _{i=1,\dots ,N} \mathbb E\left[ \sup _{0 \le s\le t} \big \vert \xi ^{i,N}_s-\bar{Y}^{i,N}_s\big \vert ^2\right] + \mathbb E\left[ \big \Vert u_t^{S^N(\xi )}-u^{m^0}_t\big \Vert _{\infty } ^2\right] \nonumber \\&\quad \le C\sup _{ \underset{\Vert \varphi \Vert _{\infty } \le 1}{\varphi \in \mathcal {C}_b(\mathcal {C}^d)}} \mathbb E\Big [ \big \vert \langle S^N({\bar{\mathbf {Y}}}) - m^0 , \varphi \big \rangle \vert ^2 \Big ], \end{aligned}$$(3.12)with again \({S^{N}({\bar{\mathbf{Y}}}) := \frac{1}{N} \sum \limits _{j=1}^N \delta _{\bar{Y}^{j,N}}}\).
Remark 3.4
The convergence of the numerical approximation \(u_t^{S^N(\xi )}\) to \(u_t^{m^0}\) only requires the convergence of \( d_2^\Omega (S^N({\bar{\mathbf {Y}}}), m^0)\) to 0, where the distance \( d_2^\Omega \) has been defined at Remark 2.6. This holds if, for each N, \(\bar{Y}^{i,N}, i=1, \ldots N\) are independent; however, this is only a sufficient condition.
This gives the opportunity to define new numerical schemes for which the convergence of the empirical measure \( S^N({\bar{\mathbf {Y}}})\) is verified without i.i.d. particles. Let us consider \((\bar{Y}^{i,N})_{i=1, \ldots N}\) (resp. \((\xi ^{i,N})_{i=1, \ldots N}\)) solutions of (3.10) (resp. (3.11)). Observe that for any real valued test function in \({\mathcal {C}}_b({\mathcal {C}}^d)\)
where \(\sigma _{\varphi }:=\sqrt{Var ( \varphi (\bar{Y}^{1,N}))}\) and \(\rho ^{i,j}_{\varphi }:= \frac{\mathbb E[\varphi (Y^{i,N})\varphi (Y^{j,N})]-\mathbb E[\varphi (Y^{i,N})]\mathbb E[\varphi (Y^{j,N})]}{\sigma ^2_{\varphi }}\).
In the specific case where \((W^{i,N})_{i=1, \ldots N}\) are independent Brownian motions then \(\rho ^{i,j}_{\varphi }=0\) for any bounded \(\varphi \in {\mathcal {C}}_b({\mathcal {C}}^d)\) and
With our error bound one can naturally investigate antithetic variables approaches to improve the interacting particle system convergence. Let us consider \(N=2N'\) and take \((W^{i,N})_{i=1, \ldots N'}\) as \(N'\) iid Brownian motions, then for the rest of the particles, for any \(j=N'+1,N'+2, \ldots 2N'\), set \(W^{j,N}=-W^{j-N',N}\). In this situation, we obtain
So, even in this case, the rate of convergence of \(u^{S^N(\xi )}_t\) to \(u^{m^0}_t\) is still of order \(1/\sqrt{N}\).
If moreover one has \(\displaystyle { \sup _{ \underset{\Vert \varphi \Vert _{\infty } \le 1}{\varphi \in \mathcal {C}_b(\mathcal {C}^d)}} \rho ^{1,1+N'}_{\varphi } \le 0 }\), the variance will also be reduced with respect to the case of independent Brownian motions, see (3.13).
Proof of Proposition 3.3
Let us fix \(t \in [0,T]\). In this proof, \(C:= C(\Phi , g, \Lambda , K, T)\) is a real positive constant, which may change from line to line.
Equation (3.10) has N blocks, numbered by \(1 \le i \le N\). Theorem 2.8 gives uniqueness in law for each block equation, which implies that for any \(i=1, \ldots N\), \(m^{i,N}=m^0\) and proves the first item.
Concerning item 2., i.e. the strong existence and pathwise uniqueness of (3.11), the same argument as for the well-statement of (3.3) operates. The only difference consists in the fact that the Brownian motions may be correlated. A very close proof to the one of Theorem 11.2 page 128 in [25] works: the main argument is the multidimensional BDG inequality, see e.g. Problem 3.29 of [18].
We discuss now item 3. proving inequality (3.12). On the one hand, since the map \((t,\bar{\xi }) \in [0,T] \times \mathcal {C}^{dN} \mapsto ~(u_t^{S^N(\bar{\xi })}(\bar{\xi }^i_t))_{i=1, \ldots ,N}\) is measurable and satisfies the non-anticipative property (3.4), the first assertion of Lemma 2.7 gives for all \(i \in \{1, \ldots ,N\}\)
which implies
We use inequalities (2.9) for \(m = S^N(\xi )(\bar{\omega })\) and \(m' = S^N({\bar{\mathbf{Y}}})(\bar{\omega })\)), where \(\bar{\omega }\) is a random realization in \(\Omega \) and (2.12) (with the random probability \( \eta = S^N({\bar{\mathbf{Y}}})\) and \(m = m^0\)) in item 5. of Proposition 2.5. This yields
where the third inequality follows from Remark 2.1.
Let us introduce the non-negative function G defined on [0, T] by
From inequalities (3.15) and (3.16) that are valid for all \(t \in [0,T]\), we obtain
By Gronwall’s lemma, for all \(t \in [0,T]\), we obtain
This concludes the proof of Proposition 3.3.\(\square \)
From now on, we prove Theorem 3.1,
Proof of Theorem 3.1
As we have mentioned above we will apply Proposition 3.3 setting for all \(i \in \{1, \ldots ,N\}\), \(W^{i,N} := W^i\). Pathwise uniqueness of systems (3.1) and (3.10) implies \(\bar{Y}^{i,N} = Y^i\) for all \(i \in \{1, \ldots ,N\}\). Taking into account (3.12) in Proposition 3.3, in order to establish inequalities (3.6) and (3.7), we need to bound the quantity \(\displaystyle {\sup _{ \underset{\Vert \varphi \Vert _{\infty } \le 1}{\varphi \in \mathcal {C}_b(\mathcal {C}^d)}} \mathbb E[ \vert \langle S^N(\mathbf {Y}) - m^0 , \varphi \rangle \vert ^2 ] } \) . This is possible via (3.13) in Remark 3.4, since \((Y^i)_{i=1, \ldots ,N}\) are i.i.d. according to \(m^0\). This concludes the proof of item 1.
It remains now to prove (3.8) in item 2. First, the inequality
holds for all \(t \in [0,T]\). Using inequality (2.11) of Proposition 2.5, for all \(t \in [0,T]\), for \(m = S^N(\xi ), m'= S^N(\mathbf {Y})\), we get
where the latter inequality is obtained through (3.7). The second term of the r.h.s. in (3.19) needs more computations. Let us fix \(i \in \{1, \ldots ,N\}\). First,
where, for all \(t \in [0,T]\)
where we recall that \(m^0\) is the common law of all the processes \(Y^i, 1 \le i \le N\).
To simplify notations, we set \(P_j(t,x) := K(x-Y^j_t) V_t\big (Y^j,u^{m^0}(Y^j)\big )-\mathbb E\big [K(x-Y^1_t) V_t\big (Y^1,u^{m^0}(Y^1)\big ) \big ]\) for all \(j \in \{1, \ldots ,N\}\), \(x \in \mathbb R^d\) and \(t \in [0,T]\).
We observe that for all \(x \in \mathbb R^d, t \in [0,T]\), \((P_j(t,x))_{j=1, \ldots ,N}\) are i.i.d. centered r.v. Hence,
By integrating each side of the inequality above w.r.t. \(x \in \mathbb R^d\), we obtain
where we have used that \(\Vert K \Vert _1 = 1\).
Concerning \(A_t(x)\), we write
where the third inequality comes from (2.7). Integrating w.r.t. \(x \in \mathbb R^d\) and taking expectation on each side of the above inequality gives us, for all \(t \in [0,T]\),
where we have used (2.12) of Proposition 2.5 for the second inequality above and (3.13) for the latter one. To conclude, it is enough to replace (3.23), (3.25) in (3.21), and inject (3.20), (3.21) into (3.19).\(\square \)
4 Particle algorithm
4.1 Time discretization of the particle system
In this section Assumption 2. is in force. Let \((Y_0^i)_{i=1, \ldots ,N}\) be i.i.d. r.v. distributed according to \(\zeta _0\). In the sequel, we are interested in discretizing the interacting particle system (3.3). \((\xi ^{i,N}, 1 \le i \le N\)) will denote again the corresponding solution. Let us consider a regular time grid \(0=t_0\le \cdots \le t_k=k\delta t\le \cdots \le t_n=T\), with \(\delta t=T/n\). We introduce the continuous \(\mathbb R^{dN}\)-valued process \((\tilde{\xi }_t)_{t\in [0,T]}\) and the family of nonnegative functions \((\tilde{u}_t)_{t\in [0,T]}\) defined on \(\mathbb R^d\) constructively such that
where \(r:\,s\in [0,T]\,\mapsto r(s)\in \{t_0, \ldots t_n\}\) is the piecewise constant function such that \(r(s)=t_k\) when \(s\in [t_k,t_{k+1}[\). We can observe that \((\tilde{\xi }^{i,N})_{i=1, \ldots ,N}\) is an adapted and continuous process. The interacting particle system \((\tilde{\xi }^{i,N})_{i=1, \ldots N}\) can be simulated perfectly at the discrete instants \((t_k)_{k=0, \ldots ,n}\) via independent standard and centered Gaussian random variables. We will show that this interacting particle system provides an approximation to the solution \((\xi ^{i,N})_{i=1, \ldots N}\), of system (3.3), which converges at a rate bounded by \( \sqrt{\delta t}\), up to a multiplicative constant.
Proposition 4.1
Let us suppose the validity of Assumption 2. The time discretized particle system (4.1) converges to the original particle system (3.3). More precisely, for all \(t \in [0,T]\), the following estimates hold:
where C is a finite positive constant only depending on \(M_K,M_{\Lambda },L_K,L_{\Lambda }, m_\Phi , m_g, T\).
If we assume moreover that \(K\in W^{1,2}(\mathbb R^d)\), then
where C is a finite positive constant only depending on \(M_K,M_{\Lambda },m_{\Phi }, m_g,L_K,L_{\Lambda },T\) and \(\Vert \nabla K\Vert _2\).
The left-hand side of (4.3) is generally known, as Mean Integrated Squared Error (MISE).
The result below states the convergence of \(\tilde{u}_t\) to \(u^{m^0}_t\) when \(\delta t \rightarrow 0\) and \(N \rightarrow + \infty \), with an explicit rate of convergence.
Theorem 4.2
We suppose Assumption 2. We indicate by \(m^0\) the law of Y, where (Y, u) is the solution of (1.4). The time discretized particle system (4.1) converges to the solution of (1.4). More precisely, we have the following. We suppose \({\mathcal F}(K) \in L^1 (\)resp. \(K\in W^{1,2}(\mathbb R^d))\). There exists a real constant \(C > 0\) such that for all \(t \in [0,T]\),
\(\Big (\)respectively
Remark 4.3
When \(\Lambda =0\) and \(\Phi \) and g are infinitely differentiable with all derivatives being bounded, Corollary 1.1 of [19] states that, for fixed smooth test function with polynomial growth \(\varphi \), one has
This leads reasonnably to the conjecture that the rate in (4.4) is not optimal and it could be replaced by \((\delta t)^2 + \frac{1}{N}\). This intuition will be confirmed by numerical simulations in Sect. 5.
Proof
We first observe that for all \(t \in [0,T]\), for \(p = \infty , 2\)
The first term in the r.h.s. of (4.7) is bounded by \(\frac{C}{N}\) using Theorem 3.1, inequality (3.6) (respectively (3.8)).
The second term of the same inequality is controlled by \(C \delta t\), through Proposition 4.1, inequality (4.2) (resp. (4.3)).\(\square \)
The proof of Proposition 4.1 relies on similar techniques used to prove Theorem 3.1. The idea is first to estimate through Lemma 4.4 the perturbation error due to the time discretization scheme of the SDE and of the integral appearing in the exponential weight in system (4.1). Later the propagation of this error through the dynamical system (3.3) will be controlled via Gronwall’s lemma. Lemma 4.4 below will be proved in the Appendix.
Lemma 4.4
Let us suppose the validity of Assumption 2. There exists a finite constant \(C>0\) only depending on \(T,M_K,m_{\Phi },m_g,L_K,L_\Phi ,L_g\) and \(M_{\Lambda },L_{\Lambda }\) such that for any \(t\in [0,T]\),
Proof of Proposition 4.1
All along this proof, C will denote a positive constant that only depends on
\(T ,M_K,m_{\Phi }, m_g, L_K,L_\Phi , L_g\) and \(M_{\Lambda }\),\(L_{\Lambda }\) and that can change from line to line. Let us fix \(t \in [0,T]\).
-
We begin by considering inequality (4.2). We first fix \(1 \le i \le N\). By (4.9) and (4.10) in Lemma 4.4 and (2.9) in Proposition 2.5, we obtain
$$\begin{aligned} \mathbb E\Big [\Big \Vert \tilde{u}_t-u^{S^N(\xi )}_t\Big \Vert _\infty ^2\Big ]\le & {} \mathbb E\Big [ \Big ( \Vert \tilde{u}_t-\tilde{u}_{r(t)} \Vert _{\infty } + \Big \Vert \tilde{u}_{r(t)}- u^{S^N(\tilde{\xi })}_t \Big \Vert _{\infty } \nonumber \\&+\, \Big \Vert u^{S^N(\tilde{\xi })}_t - u^{S^N(\xi )}_t \Big \Vert _{\infty } \Big )^2 \Big ] \nonumber \\\le & {} 3(\mathbb E[\Vert \tilde{u}_t-\tilde{u}_{r(t)} \Vert _{\infty }^2] + \mathbb E\Big [\Big \Vert \tilde{u}_{r(t)}-u_t^{S^N( \tilde{\xi })}\Big \Vert _{\infty }^2\Big ]\nonumber \\&+\, \mathbb E\Big [\Big \Vert u_t^{S^N(\tilde{\xi })}-u_t^{S^N(\xi )}\Big \Vert _\infty ^2\Big ])\nonumber \\\le & {} C\delta t +C\mathbb E\big [\big \vert W_t\big (S^N(\tilde{\xi }),S^N(\xi )\big )\big \vert ^2\big ]\nonumber \\\le & {} C\delta t +C\sup _{i=1, \ldots , N} \mathbb E\Big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\Big ]\ , \end{aligned}$$(4.11)where the function \(u^{S^N(\tilde{\xi })}\) makes sense since \( \tilde{\xi }\) has almost surely continuous trajectories and so \(S^N(\tilde{\xi })\) is a random probability in \(\mathcal {P}(\mathcal {C}^d)\). Besides, by the second assertion of Lemma 2.7, setting \(Y' := \tilde{\xi }^{i,N}\), \(r_1(s) = r(s)\) and \(Y := \xi ^{i,N}\), \(r_2(s) = s\), we get
$$\begin{aligned} \mathbb E\Big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\Big ]&\le C \mathbb E\left[ \int _0^t \big \vert \tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )-u_s^{S^N(\xi )}\big (\xi ^{i,N}_s\big )\big \vert ^2\,ds\right] \nonumber \\&\quad +\, C \int _0^t \mathbb E\left[ \big \vert \tilde{\xi }^{i,N}_{r(s)} - \tilde{\xi }^{i,N}_{s} \big \vert ^2 \right] ds + C \delta t \ . \end{aligned}$$(4.12)Concerning the first term in the r.h.s. of (4.12), we have for all \(s \in [0,T]\)
$$\begin{aligned} \big \vert \tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )-u_s^{S^N(\xi )}\big (\xi ^{i,N}_s\big )\big \vert ^2&\le 2 \big \vert \tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )-u_s^{S^N(\xi )}\big (\tilde{\xi }^{i,N}_{r(s)}\big )\big \vert ^2 \nonumber \\&\quad +\, 2 \big \vert u_s^{S^N(\xi )}\big (\tilde{\xi }^{i,N}_{r(s)}\big )-u_s^{S^N(\xi )}\big (\xi ^{i,N}_s\big )\big \vert ^2 \nonumber \\&\le 2 \Big \Vert \tilde{u}_{r(s)} - u^{S^N(\xi )}_s \Big \Vert _{\infty }^2 + 2 C \Big \vert \tilde{\xi }^{i,N}_{r(s)} - \xi ^{i,N}_s \Big \vert ^2 \ ,\nonumber \\ \end{aligned}$$(4.13)where the second inequality above follows by (2.9) in Proposition 2.5, setting \(m = m' = S^N(\xi )\). Consequently, by (4.12)
$$\begin{aligned} \mathbb E\big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\big ]\le & {} C \left\{ \mathbb E\left[ \int _0^t \big \Vert \tilde{u}_{r(s)}-u_s^{S^N(\xi )}\big \Vert ^2_{\infty } \,ds \right] + \int _0^t \mathbb E\left[ \big \vert \tilde{\xi }^{i,N}_{r(s)}-\xi _{s}^{i,N} \big \vert ^2 \right] \,ds + \delta t \right\} \nonumber \\\le & {} C \left\{ \mathbb E\left[ \int _0^t \Vert \tilde{u}_{r(s)}- \tilde{u}_s \Vert ^2_{\infty }\,ds\right] + \mathbb E\left[ \int _0^t \big \Vert \tilde{u}_s-u_s^{S^N(\xi )}\big \Vert ^2_{\infty }\,ds\right] \right. \nonumber \\&\left. +\, \mathbb E\left[ \int _0^t\big \vert \tilde{\xi }^{i,N}_{r(s)}- \tilde{\xi }^{i,N}_s\big \vert ^2\,ds\right] + \mathbb E\left[ \int _0^t\big \vert \tilde{\xi }^{i,N}_{s}- \xi ^{i,N}_s\big \vert ^2\,ds\right] + \delta t \right\} .\nonumber \\ \end{aligned}$$(4.14)Using inequalities (4.8) and (4.9) in Lemma 4.4, for all \(t \in [0,T]\), we obtain
$$\begin{aligned} \sup _{i=1, \ldots , N}\mathbb E\big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\big ]\le & {} C\delta t +C \int _0^t \left[ \mathbb E\big [\big \Vert \tilde{u}_{s}-u_s^{S^N(\xi )}\big \Vert ^2_{\infty }\big ]\right. \nonumber \\&\left. + \sup _{i=1, \ldots , N}\mathbb E\big [\sup _{\theta \le s} \big \vert \tilde{\xi }^{i,N}_\theta -\xi ^{i,N}_\theta \big \vert ^2\big ]\right] \,ds.\nonumber \\ \end{aligned}$$(4.15)Gathering the latter inequality together with (4.11) yields
$$\begin{aligned}&\mathbb E\big [\big \Vert \tilde{u}_t-u^{S^N(\xi )}_t\big \Vert _\infty ^2\big ] + \sup _{i=1, \ldots , N}\mathbb E\big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\big ]\nonumber \\&\quad \le C\delta t + 2C\sup _{i=1, \ldots , N} \mathbb E\big [\sup _{s\le t} \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\vert ^2\big ] \le C\delta t \nonumber \\&\qquad + \; C \int _0^t \Big [\mathbb E\big [\big \Vert \tilde{u}_{s}-u_s^{S^N(\xi )}\big \Vert ^2_{\infty }\big ] \nonumber \\&\qquad + \sup _{i=1, \ldots , N}\mathbb E\big [\sup _{\theta \le s} \big \vert \tilde{\xi }^{i,N}_\theta -\xi ^{i,N}_\theta \big \vert ^2\big ]\Big ] ds \ . \end{aligned}$$(4.16)Applying Gronwall’s lemma to the function
$$\begin{aligned} t\mapsto \sup _{i=1, \ldots , N}\mathbb E\big [\sup _{s\le t} \big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\big ]+\mathbb E\Big [\Big \Vert \tilde{u}_{t}-u_t^{S^N(\xi )}\Big \Vert ^2_{\infty }\Big ] \end{aligned}$$ends the proof of (4.2).
-
We focus now on (4.3). First we observe that
$$\begin{aligned} \mathbb E\Big [\Big \Vert \tilde{u}_t-u^{S^N(\xi )}_t\Big \Vert _2^2\Big ]\le 2\mathbb E\Big [\Big \Vert \tilde{u}_t-u_t^{S^N(\tilde{\xi })}\Big \Vert _2^2\Big ]+2\mathbb E\Big [\Big \Vert u_t^{S^N(\tilde{\xi })}-u_t^{S^N(\xi )}\Big \Vert _2^2\Big ]\ . \end{aligned}$$(4.17)Using successively item 4. of Proposition 2.5, Remark 2.1 and inequality (4.2), we can bound the second term on the r.h.s. of (4.17) as follows:
$$\begin{aligned} \mathbb E\Big [\Big \Vert u_t^{S^N(\tilde{\xi })}-u_t^{S^N(\xi )}\Big \Vert _2^2\Big ]\le & {} C\mathbb E\Big [\Big \vert W_t\big (S^N(\tilde{\xi }),S^N(\xi )\big )\Big \vert ^2\Big ] \nonumber \\\le & {} C\sup _{i=1, \ldots , N}\mathbb E\Big [\sup _{s\le t}\big \vert \tilde{\xi }^{i,N}_s-\xi ^{i,N}_s\big \vert ^2\Big ] \nonumber \\\le & {} C\delta t\ . \end{aligned}$$(4.18)To simplify the notations, we introduce the real valued random variables
$$\begin{aligned} V_t^i := e^{\int _0^t\Lambda \big (s,\tilde{\xi }^{i,N}_{s},u^{S^N(\tilde{\xi })}_{s}(\tilde{\xi }^{i,N}_{s})\big )ds}\quad \text {and}\quad \tilde{V}_t^i := e^{\int _0^t\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds}\ ,\nonumber \\ \end{aligned}$$(4.19)defined for any \(i=1, \ldots N\) and \(t\in [0,T]\). Concerning the first term on the r.h.s. of (4.17), inequality (6.2) of Lemma 5.1 in the Appendix gives for all \(y \in \mathbb R^d\)
$$\begin{aligned} \Big \vert \tilde{u}_{t}(y)-u_t^{S^N(\tilde{\xi })}(y)\Big \vert ^2 \le \frac{M_K}{N}\sum _{i=1}^N K(y-\tilde{\xi }^{i,N}_t) \big \vert \tilde{V}_t^i-V_t^i \big \vert ^2 \ . \end{aligned}$$(4.20)Integrating the inequality (4.20) with respect to y, yields
$$\begin{aligned} \Big \Vert \tilde{u}_t - u_t^{S^N(\tilde{\xi })} \Big \Vert _2^2 = \int _{\mathbb R^d} \Big \vert \tilde{u}_{t}(y)-u_t^{S^N(\tilde{\xi })}(y)\Big \vert ^2\,dy \le \frac{M_K}{N}\sum _{i=1}^N \big \vert \tilde{V}_t^i - V_t^i \big \vert ^2\ , \end{aligned}$$which, in turn, implies
$$\begin{aligned} \mathbb E\left[ \Big \Vert \tilde{u}_t - u^{S^N(\tilde{\xi })}_t \Big \Vert _2^2 \right] \le \frac{M_K}{N}\sum _{i=1}^N \mathbb E\left[ \big \vert \tilde{V}_t^i - V_t^i \big \vert ^2 \right] \ . \end{aligned}$$(4.21)Using successively item 1. of Lemma 5.1 and inequality (4.8) of Lemma 4.4, for all \(i \in \{1, \ldots ,N\}\), we obtain
$$\begin{aligned} \mathbb E\big [\big \vert \tilde{V}_t^i-V_t^i \big \vert ^2\big ]\le & {} C\delta t + C\mathbb E\left[ \int _0^t \Big \vert \tilde{\xi }^{i,N}_{r(s)} - \tilde{\xi }^{i,N}_{s} \Big \vert ^2 \ ds \right] \nonumber \\&+\, C \mathbb E\left[ \int _0^t \Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)})-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_s\Big )\Big \vert ^2 ds \right] \nonumber \\\le & {} C\delta t + C \mathbb E\left[ \int _0^t \Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_s\Big )\Big \vert ^2 ds \right] \nonumber \\\le & {} C\delta t + C \mathbb E\left[ \int _0^t \Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )\Big \vert ^2 ds \right] \nonumber \\&+ \; C \mathbb E\left[ \int _0^t \Big \vert u_{s}^{S^N(\tilde{\xi })}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_{s}\Big )\Big \vert ^2 ds \right] \nonumber \\\le & {} C\delta t +C\int _0^t \left[ \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] + \mathbb E\Big [\Big \vert \tilde{\xi }^{i,N}_{r(s)}-\tilde{\xi }^{i,N}_s\Big \vert ^2\Big ] \right] \, ds\nonumber \\\le & {} C\delta t +C\int _0^t \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] \, ds\ , \end{aligned}$$(4.22)where the fourth inequality above follows from Proposition 2.5, see (2.9). Consequently using (4.22) and inequality (4.10) of Lemma 4.4, (4.21) becomes
$$\begin{aligned}&\mathbb E\Big [\Big \Vert \tilde{u}_t-u_t^{S^N(\tilde{\xi })}\Big \Vert _2^2\Big ] \le \frac{C}{N}\sum _{i=1}^N \mathbb E\big [\big \vert \tilde{V}_t^i - V_t^i \big \vert ^2\big ] \underbrace{\le }_{(4.22)} C\delta t\nonumber \\&\quad +\,C\int _0^t \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] \underbrace{\le }_{(4.10)} C\delta t. \end{aligned}$$(4.23)Finally, injecting (4.23) and (4.18) in (4.17) yields
$$\begin{aligned} \mathbb E\Big [\Big \Vert \tilde{u}_t-u^{S^N(\xi )}_t\Big \Vert _2^2\Big ] \le C \delta t \ , \end{aligned}$$
which ends the proof of Proposition 4.1.\(\square \)
4.2 Algorithm description
In this section, we describe precisely the algorithm relying on the time-discretization (4.1) of the interacting particle system (3.3). Let \(v_0\) be the law density of \(Y_0\) where Y is the solution of (1.4). In the sequel, we will make use of the same notations as in previous section. In particular, \(0=t_0\le \cdots \le t_k=k\delta t\le \cdots \le t_n=T\) is a regular time grid with \(\delta t=T/n\). We consider a real-valued function \(K : \mathbb R^d \rightarrow \mathbb R\) being a mollifier depending on some bandwith parameter \(\varepsilon \).
-
Initialization for \(k=0\).
-
1.
Generate \(\Big (\tilde{\xi }_{t_0}^{i,N}\Big )_{i=1,\ldots ,N}\) i.i.d.\(\sim \) \(v_0(x)dx\);
-
2.
set \(G_0^i := 1\), \(i = 1, \ldots ,N\);
-
3.
set \(\tilde{u}_{t_0}(\cdot ) := (K *v_0)(\cdot )\);
-
1.
-
Iterations for k = 0, \(\ldots , n-1\).
- \(\bullet \) :
-
Independently for each particle \( { \tilde{\xi }^{j,N}_{t_k}}\) for \(j=1, \ldots N\),
$$\begin{aligned} \tilde{\xi }^{j,N}_{t_{k+1}}= {\tilde{\xi }^{j,N}_{t_k}} + \Phi \Big (t_{k},{\tilde{\xi }^{j,N}_{t_k}},{\tilde{u}}_{t_{k}}\Big ({\tilde{\xi }^{j,N}_{t_k}}\Big )\Big ) \sqrt{\delta t} \epsilon ^j_{k+1} + g\Big (t_{k},{\tilde{\xi }^{j,N}_{t_k}},{\tilde{u}}_{t_{k}}\Big ({\tilde{\xi }^{j,N}_{t_k}}\Big )\Big ) \delta t \; , \end{aligned}$$where \((\epsilon ^j_{k})_{j=1, \ldots , N, k=1, \ldots n}\) is a sequence of i.i.d centered and standard Gaussian variables;
- \(\bullet \) :
-
set for \(j=1, \ldots N\),
$$\begin{aligned} G_{k+1}^j := G_{k}^j \times \exp \left( \Lambda \Big (t_{k},{ \tilde{\xi }^{j,N}_{k}},{\tilde{u}}_{t_k}\Big ({ \tilde{\xi }^{j,N}_{t_k}}\Big )\Big ) \delta t \right) ; \end{aligned}$$ - \(\bullet \) :
-
set
$$\begin{aligned} {\tilde{u}}_{t_{k+1}}(\cdot ) = {\displaystyle \frac{1}{N} \sum _{j=1}^{N} G_{k+1}^j \times K\left( \cdot - { \tilde{\xi }^{j,N}_{t_{k+1}}}\right) }. \end{aligned}$$
Remark 4.5
For a fixed \(k \in \{0, \ldots ,n-1 \}\), we observe that the simulation of the j-th particle \(\tilde{\xi }^{j,N}_{t_{k+1}}\) at time \(t_{k+1}\) involves the whole particle system through the evaluation of \(\tilde{u}_{t_k}(\tilde{\xi }_{t_k}^{j,N})\), which implies a complexity of the algorithm of order \(n N^2\).
5 Numerical results
5.1 Preliminary considerations
One motivating issue of this section is how the interacting particle system \(\xi := (\xi ^{i, N,\varepsilon })\) defined in (3.3) with \(K = K^{\varepsilon }\), \(K^{\varepsilon }(x) := \frac{1}{\varepsilon ^d}\phi ^d(\frac{x}{\varepsilon })\) for some mollifier \(\phi ^d\), can be used to approach the solution v of the PDE
to which we can reasonably expect that (1.5) converges when \(K^{\varepsilon } \xrightarrow [\varepsilon \rightarrow 0]{} \delta \).
Two significant parameters, i.e. \(\varepsilon \rightarrow 0\), \(N \rightarrow + \infty \), intervene. We expect to approximate v by \(u^{\varepsilon ,N}\), which is the solution of the Eq. (1.6), associated with the empirical measure \(m = S^N(\xi )\). To this purpose, we want to control empirically the Mean Integrated Squared Error (MISE) between the solution v of (5.1) and the particle approximation \(u^{\varepsilon ,N}\), i.e. for \(t \in [0,T]\),
where \(u^{\varepsilon } = u^{m^0}\) with \(K = K^{\varepsilon }\), \(m^0\) being the common law of processes \(Y^i, \; 1 \le i \le N\) in (3.1). Even though the second term in the r.h.s. of (5.2) does not explicitely involve the number of particles N, the first term crucially depends on both parameters \(\varepsilon , N\). The behavior of the first term relies on the propagation of chaos. This phenomenon has been observed in Corollary 3.2, which is a consequence of Theorem 3.1, for a fixed \(\varepsilon > 0\), when \(N \rightarrow + \infty \). According to Theorem 3.1, the first error term on the r.h.s. of the above inequality can be bounded by \(\frac{C(\varepsilon )}{N}\).
Concerning the second error term, no result is available but we expect that it converges to zero when \(\varepsilon \rightarrow 0\). To control the MISE, it remains to determine a relation \(N \mapsto \varepsilon (N)\) such that
When the coefficients \(\Phi \), g and the initial condition are smooth with \(\Phi \) non-degenerate and \(\Lambda \equiv 0\) (i.e. in the conservative case), Theorem 2.7 of [17] gives a description of such a relation.
In our empirical analysis, we have concentrated on a test case, for which we have an explicit solution.
We first illustrate the chaos propagation for fixed \(\varepsilon > 0\), i.e. the result of Theorem 3.1. On the other hand, we give an empirical insight concerning the following:
-
the asymptotic behavior of the second error term in inequality (5.2) for \(\varepsilon \rightarrow 0\);
-
the tradeoff \(N \mapsto \varepsilon (N)\) verifying (5.3).
Moreover, the simulations reveal two behaviors regarding the chaos propagation intensity.
5.2 The target PDE
We describe now the test case. For a given triple \((m,\mu , A)\in ]1,\infty [\times \mathbb R^d\times \mathbb R^{d \times d}\) we consider the following nonlinear PDE of the form (5.1):
where the functions \(\Phi \,,\,g\,,\, \Lambda \) defined on \([0,T]\times \mathbb R^d\times \mathbb R\) are such that
\(I_d\) denoting the identity matrix in \(\mathbb R^{d \times d}\),
Here \(f_{\mu ,A}:\mathbb R^d \rightarrow \mathbb R\) is given by
and \(B_m\) is the d-dimensional Barenblatt-Pattle density associated to \(m>1\), i.e.
with \(\alpha =\frac{d}{(m-1)d+2}\ ,\) \(\beta =\frac{\alpha }{d} \ ,\) \(\kappa =\frac{m-1}{m}\beta \) and \(D =[2\kappa ^{-\frac{d}{2}}\frac{\pi ^{\frac{d}{2}}\Gamma (\frac{m}{m-1})}{\Gamma (\frac{d}{2}+\frac{m}{m-1})} ]^{\frac{2(1-m)}{2+d(m-1)}}\ . \)
In the specific case where A is the zero matrix of \(\mathbb R^{d \times d}\), then \(f_{\mu ,A}\equiv 1\); \(g\equiv 0\) and \(\Lambda \equiv 0\). Hence, we recover the conservative porous media equation, whose explicit solution is
see [1]. For general values of \(A\in \mathbb R^{d \times d}\), extended calculations produce the following explicit solution
of (5.4), which is non conservative.
5.3 Details of the implementation
Once fixed the number N of particles, we have run \(M=100\) i.i.d. particle systems producing \((u^{\varepsilon ,N,i})_{i=1, \ldots M}\), which are M i.i.d. realizations of \(u^{\varepsilon ,N}\) introduced just after (5.1). The MISE is then approximated by the Monte Carlo approximation
where \((X^j)_{j=1, \ldots , Q=1000}\) are i.i.d \(\mathbb R^d\)-valued random variables with common density \(v(0,\cdot )\). In our simulation, we have chosen \(T=1\), \(m=3/2\), \(\mu =0\) and \(A=\frac{2}{3} I_d\). \(K^{\varepsilon }=\frac{1}{\varepsilon ^d}\phi ^d(\frac{\cdot }{\varepsilon })\) with \(\phi ^d\) being the standard and centered Gaussian density.
In this subsection, we fix the dimension to \(d = 5\). We have run a discretized version of the interacting particle system with Euler scheme mesh kT / n with \(n=10\). Notice that this discretization error is neglected in the present analysis.
Our simulations show that the approximation error presents two types of behavior depending on the number N of particles with respect to the regularization parameter \(\varepsilon \).
-
1.
For large values of N, we visualize a chaos propagation behavior for which the error estimates are similar to the ones provided by the density estimation theory [26] corresponding to the classical framework of independent samples.
-
2.
For small values of N appears a transient behavior for which the bias and variance errors cannot be easily described.
Observe that the Mean Integrated Squared Error \(\mathrm{MISE}_t(\varepsilon ,N):=\mathbb E[ \Vert u_t^{\varepsilon ,N}-v_t\Vert _2^2 ]\) can be decomposed as the sum of the variance \( V_t(\varepsilon ,N)\) and squared bias \(B_t^2(\varepsilon ,N)\) as follows:
For N large enough, according to Corollary 3.2, one expects that the propagation of chaos holds. Then the particle system \((\xi ^{i,N})_{i=1, \ldots , N}\) (solution of (3.3)) is close to an i.i.d. system with common law \(m^0\). We observe that, in the specific case where the weighting function \(\Lambda \) does not depend on the density u, for \(t \in [0,T]\), we have
Therefore, under the chaos propagation behavior, the approximations below hold for the variance and the squared bias:
We recall that the relation \(u^{\varepsilon } = K^{\varepsilon } *v^{\varepsilon }\) comes from Theorem 6.1 of [20], where \(v^{\varepsilon }\) is solution of (1.5) with \(K = K^{\varepsilon }\).
On Fig. 1, we have reported the estimated variance error \(V_t(\varepsilon ,N)\) as a function of the particle number N, (on the left graph) and as a function of the regularization parameter \(\varepsilon \), (on the right graph), for \(t = T=1\) and \(d=5\). We have used for this a similar Monte Carlo approximation as (5.10).
Variance error as a function of the number of particles, N, and the mollifier window width, \(\varepsilon \), for dimension \(d=5\) at the final time step \(T=1\)
That figure shows that, when the number of particles is large enough, the variance error behaves precisely as in the classical case of density estimation encountered in [26], i.e., vanishing at a rate \(\frac{1}{N\varepsilon ^d}\), see relation (4.10), Chapter 4., Sect. 4.3.1. This is in particular illustrated by the log-log graphs, showing almost linear curve, when N is sufficiently large. In particular we observe the following.
-
On the left graph, \(\log (V_t(\varepsilon ,N)) \approx a-\alpha \log N\) with slope \(\alpha =1\);
-
On the right graph, \(\log V_t(\varepsilon ,N) \approx b-\beta \log \varepsilon \) with slope \(\beta =5=d\).
It seems that the threshold N after which appears the linear behavior (compatible with the propagation of chaos situation corresponding to asymptotic-i.i.d. particles) decreases when \(\varepsilon \) grows. In other words, when \(\varepsilon \) is large, less particles N are needed to give evidence to the chaotic behavior.
This phenomenon can be probably explained by analyzing the particle system dynamics. Indeed, at each time step, the interaction between the particles is due to the empirical estimation of \(u^\varepsilon = K^\varepsilon *v^\varepsilon \) based on the particle system. Intuitively, the more accurate the approximation \(u^{\varepsilon ,N}\) of \(u^{\varepsilon }\) is, the less strong the interaction between particles will be. In the limiting case when \(u^{\varepsilon ,N}=u^{\varepsilon }\), the interaction disappears.
Now observe that at time step 0, the particle system \(({\xi }^{i,N}_0)\) is i.i.d. according to \(v_0(\cdot )\), so that the estimation of \((K^\varepsilon *v^\varepsilon )(0,\cdot )\) provided by (4.1) reduces to the classical density estimation approach, see [26] as mentioned above. In that classical framework, we emphasize that, for larger values of \(\varepsilon \), the number of particles, needed to achieve a given density estimation accuracy, is smaller. Hence, one can imagine that for larger values of \(\varepsilon \) less particles will be needed to obtain a quasi-i.i.d particle system at time step 1, \(({\xi }^{i,N}_{t_1})\). We can then reasonably presume that this initial error propagates along the time steps.
On Fig. 2, we have reported the estimated squared bias error, \(B^2_t(\varepsilon ,N)\), as a function of the regularization parameter, \(\varepsilon \), for different values of the particle number N, for \(t = T=1\) and \(d=5\).
Bias error as a function of the mollifier window width, \(\varepsilon \), for dimension \(d=5\) at the final time step \(T=1\)
One can observe that, similarly to the classical i.i.d. case, (see relation (4.9) in Chapter 4, Sect. 4.3.1 in [26]), for N large enough, the bias error does not depend on N and can be approximated by \(a \varepsilon ^4\), for some constant \(a>0\). This is in fact coherent with the bias approximation (5.13), developed in the specific case where the weighting function \(\Lambda \) does not depend on the density. Assuming the validity of approximation (5.13) and of the previous empirical observation implies that one can bound the error between the solution, \(v^\varepsilon \), of the regularized PDE of the form (1.5) (with \(K = K^{\varepsilon }\)) associated to (5.4), and the solution, v, of the limit (non regularized) PDE (5.4) as follows
Indeed, at least, the first term in the second line can be easily bounded, supposing that \(v_t^\varepsilon \) has a bounded second derivative. This constitutes an empirical proof of the fact that \(v^\varepsilon \) converges to v.
As observed in the variance error graphs, the threshold N, above which the propagation of chaos behavior is observed decreases with \(\varepsilon \). Indeed, for \(\varepsilon >0.6\) we observe a chaotic behavior of the bias error, starting from \(N\ge 500\), whereas for \(\varepsilon \in [0.4,0.6]\), this chaotic behavior appears only for \(N\ge 5000\).
For small values of \(\varepsilon \le 0.6\), the bias highly depends on N for any \(N\le 10^4\); moreover that dependence becomes less relevant when N increases. This is probably due to the combination of two effects: the lack of chaos propagation phenomenon and the fact that the coefficient \(\Lambda \) depends on u, so that (5.12) does not hold in that context.
Taking into account both the bias and the variance error in the MISE (5.11), the choice of \(\varepsilon \) has to be carefully optimized w.r.t. the number of particles: \(\varepsilon \) going to zero together with N going to infinity at a judicious relative rate seem to ensure the convergence of the estimated MISE to zero. This kind of tradeoff is standard in density estimation theory and was already investigated theoretically in the context of forward interacting particle systems related to conservative regularized nonlinear PDE in [17]. Extending this type of theoretical analysis to our non conservative framework is beyond the scope of the present paper.
5.3.1 Time discretization error
In this subsection, we are interested in analysing via numerical simulations the time discretization error w.r.t. to \(\delta t ={T}/{n}\). As announced in Remark 4.3, we suspect that the rate in (4.4) is not optimal and that the MISE error induced by the time discretization is of order \(1/{n}^2\) instead of 1 / n.
Let \(\tilde{u}^{\varepsilon , N, n}_T\) denote the particle approximation obtained by scheme (4.1) with a number of particles, N, a regularization parameter, \(\varepsilon \), and a number of time steps, n. In order to focus on the time discretization error apart from the particle approximation and the regularization error (related to N and \(\varepsilon \)), we have considered errors of the type \(\mathbb E[\Vert \tilde{u}^{\varepsilon , N, n}_T-\tilde{u}_T^{\varepsilon , N, n_0}\Vert ^2_2]\) for different numbers of time steps \(n<n_0\) where \(n_0\) is supposed to be a large number of time steps. More precisely, we have decomposed this error into a variance and a squared bias term as
if \(u^{\varepsilon , N, n}_T\) and \(u^{\varepsilon , N, n_0}_T \) are independent.
On Fig. 3, we have reported the Monte Carlo estimation (according to (5.10), with \(Q=1000\) runs) of the above variance and squared bias terms in a log–log scale in order to diagnose the expected rate of convergence \(1/{n}^2\) via a straight line with slope \(-2\). All the parameters are similar to the simulations performed in previous subsection excepted for the dimension \(d=1, N = 5000\) and \(n_0\) is set to 1000 time steps. One can observe that the variance term (in dashed lines) seems not to depend on the number of time steps n whereas the squared bias term decreases as expected at a rate close to \(1/n^2\).
Variance and squared bias error (5.15) as a function of the number of time steps, \(n=5,10,20,40,80,160,320\), at the final time step \(T=1\) (with dimension \(d=1\), \(N=5000\) particles and \(\varepsilon =0.3\) or 0.9)
References
Barenblatt, G.I.: On some unsteady motions of a liquid and gas in a porous medium. Akad. Nauk. SSSR Prikl. Mat. Meh. 16, 67–78 (1952)
Belaribi, N., Cuvelier, F., Russo, F.: A probabilistic algorithm approximating solutions of a singular PDE of porous media type. Monte Carlo Methods Appl. 17(4), 317–369 (2011)
Belaribi, N., Cuvelier, F., Russo, F.: Probabilistic and deterministic algorithms for space multidimensional irregular porous media equation. SPDEs Anal. Comput. 1(1), 3–62 (2013)
Ben Alaya, M., Jourdain, B.: Probabilistic approximation of a nonlinear parabolic equation occurring in rheology. J. Appl. Probab. 44(2), 528–546 (2007)
Bertsekas, D.P., Shreve, S.E.: Stochastic optimal control. In: Mathematics in Science and Engineering, vol. 139. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, (1978) (The discrete time case)
Bossy, M., Jourdain, B.: Rate of convergence of a particle method for the solution of a 1D viscous scalar conservation law in a bounded interval. Ann. Probab. 30(4), 1797–1832 (2002)
Bossy, M., Talay, D.: A stochastic particle method for some one-dimensional nonlinear p.d.e. Math. Comput. Simul., 38(1–3):43–50 (1995) (Probabilités numériques (Paris, 1992))
Bossy, M., Talay, D.: A stochastic particle method for the McKean–Vlasov and the Burgers equation. Math. Comput. 66(217), 157–192 (1997)
Bouchard, B., Touzi, N.: Discrete-time approximation and Monte Carlo simulation of backward stochastic differential equations. Stoch. Process. Appl. 111, 175–206 (2004)
Cheridito, P., Soner, H.M., Touzi, N., Victoir, N.: Second-order backward stochastic differential equations and fully nonlinear parabolic PDEs. Commun. Pure Appl. Math. 60(7), 1081–1110 (2007)
Crauel, H.: Random probability measures on Polish spaces. In: Stochastics Monographs, vol. 11. Taylor & Francis, London (2002)
Del Moral, P.: Feynman-Kac formulae: genealogical and interacting particle systems with applications. In: Probability and Its Applications (New York). Springer-Verlag, New York (2004)
Del Moral, P.: Mean field simulation for Monte Carlo integration. In: Monographs on Statistics and Applied Probability, vol. 126. CRC Press, Boca Raton (2013)
Gobet, E., Lemor, J.-P., Warin, X.: A regression-based Monte Carlo method to solve backward stochastic differential equations. Ann. Appl. Probab. 15(3), 2172–2202 (2005)
Henry-Labordère, P.: Counterparty risk valuation: a marked branching diffusion approach. doi:10.2139/ssrn.1995503 or http://ssrn.com/abstract=1995503 (2012)
Henry-Labordère, P., Tan, X., Touzi, N.: A numerical algorithm for a class of BSDEs via the branching process. Stoch. Process. Appl. 124(2), 1112–1140 (2014)
Jourdain, B., Méléard, S.: Propagation of chaos and fluctuations for a moderate model with smooth initial data. Ann. Inst. H. Poincaré Probab. Statist. 34(6), 727–766 (1998)
Karatzas, I., Shreve, S.E.: Brownian motion and stochastic calculus. In: Graduate Texts in Mathematics, vol. 113, 2nd edn. Springer-Verlag, New York (1991)
Kohatsu-Higa, A., Ogawa, S.: Weak rate of convergence for an Euler scheme of nonlinear SDE’s. Monte Carlo Methods Appl. 3(4), 327–345 (1997)
Le Cavil, A., Oudjane, N., Russo, F.: Probabilistic representation of a class of non conservative nonlinear partial differential equations. https://hal.archives-ouvertes.fr/hal-01241701 (2015)
McKean, H.P., Jr.: Propagation of chaos for a class of non-linear parabolic equations. In: Stochastic Differential Equations (Lecture Series in Differential Equations, Session 7, Catholic Univ., 1967). Air Force Office Sci. Res., Arlington, pp. 41–57 (1967)
Pardoux, E.: Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic PDEs of second order. In: Stochastic Analysis and Related Topics, VI (Geilo, 1996), vol. 42 of Progr. Probab. Birkhäuser Boston, Boston, MA, pp. 79–127 (1998)
Pardoux, É., Peng, S.G.: Adapted solution of a backward stochastic differential equation. Syst. Control Lett. 14(1), 55–61 (1990)
Pardoux, E., Raşcanu, A.: Stochastic Differential Equations, Backward SDEs, Partial Differential Equations, vol. 69. Springer, Berlin (2014)
Rogers, L.C.G., Williams, D.: Diffusions, Markov Processes, and Martingales, vol. 2. Cambridge Mathematical Library. Cambridge University Press, Cambridge, (2000). (Itôcalculus, Reprint of the second (1994) edition)
Silverman, B.W.: Density Estimation forStatistics and Data Analysis. Monographs on Statistics and Applied Probability. Chapman & Hall, London (1986)
Sznitman, A-S.: Topics in propagation of chaos. In: École d’Été de Probabilités de Saint-Flour XIX—1989. Lecture Notes in Mathematics, vol. 1464. Springer, Berlin, pp. 165–251 (1991)
Talay, D.: Probabilistic numerical methods for partial differential equations: elements of analysis. In: Probabilistic Models for Nonlinear Partial Differential Equations (Montecatini Terme, 1995). Lecture Notes in Mathematics, vol. 1627. Springer, Berlin, pp. 148–196 (1996)
Acknowledgments
The authors are very grateful to the anonymous Referee for her/his careful reading of the paper and the suggestions which have largely contributed to improve the first submitted version. The third named author has benefited partially from the support of the “FMJH Program Gaspard Monge in optimization and operation research” (Project 2014-1607H).
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
In this appendix, we present the proof of Lemma 4.4. We first proceed with the proof of some intermediary inequalities.
Lemma 5.1
We suppose Assumption 1. Let \(N \in \mathbb N^{\star }\). Let \((\xi ^{i,N})_{i=1, \ldots ,N}\) be (a solution of) the interacting particle system (3.3); let \((\tilde{\xi }^{i,N})_{i=1, \ldots ,N}\) and \(\tilde{u}\) as defined as in the discretized interacting particle system (4.1).
The random variables \(V_t^i := e^{\int _0^t\Lambda \big (s,\tilde{\xi }^{i,N}_{s},u^{S^N(\tilde{\xi })}_{s}(\tilde{\xi }^{i,N}_{s})\big )ds}\) and \( \tilde{V}_t^i := e^{\int _0^t\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds}\), for all \(t \in [0,T]\), \(i \in \{ 1, \ldots ,N\}\) fulfill the following.
-
1.
For all \(t \in [0,T]\), \(i \in \{1, \ldots ,N\}\)
$$\begin{aligned} \mathbb E\big [\big \vert \tilde{V}_t^i-V_t^i \big \vert ^2\big ]&\le C\delta t + C\mathbb E\left[ \int _0^t \big \vert \tilde{\xi }^{i,N}_{r(s)} - \tilde{\xi }^{i,N}_{s} \big \vert ^2 \ ds \right] \nonumber \\&\quad +\, C \mathbb E\left[ \int _0^t \big \vert \tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )-u^{S^N(\tilde{\xi })}_s\big (\tilde{\xi }^{i,N}_s\big )\big \vert ^2 ds \right] , \end{aligned}$$(6.1)where C is a real positive constant depending only on \(M_{\Lambda }\), \(L_{\Lambda }\) and T.
-
2.
For all \((t,y) \in [0,T] \times \mathbb R^d\), \(i \in \{1, \ldots ,N\}\)
$$\begin{aligned} \big \vert \tilde{u}_{t}(y)-u_t^{S^N(\tilde{\xi })}(y)\big \vert ^2 \le \frac{M_K}{N}\sum _{i=1}^N K\big (y-\tilde{\xi }^{i,N}_t\big ) \; \big \vert \tilde{V}_t^i-V_t^i \big \vert ^2 \ . \end{aligned}$$(6.2)
Proof of Lemma 5.1
Let us fix \(t \in [0,T]\), \(i \in \{1, \ldots ,N\}\). To prove (6.1), it is enough to recall that \(\Lambda \) being Lipschitz w.r.t. the space variables and \(\frac{1}{2}\)-Holder continuous w.r.t. the time variable, the inequality (2.6) yields
and taking the expectation in both sides of (6.3) implies (6.1) with \(C := 3e^{2TM_{\Lambda }}L^2_{\Lambda }\).
Let us fix \(y \in \mathbb R^d\). Concerning (6.2), by recalling the third line equation of (4.1) and the equation (1.6) (with \(m = S^N(\tilde{\xi })\)), we have
which concludes the proof of (6.2) and therefore of Lemma 5.1.\(\square \)
Proof of Lemma 4.4
All along this proof, C will denote a positive constant that only depends
\(T,M_K,m_{\Phi },m_g,L_K,L_\Phi ,L_g\) and \(M_{\Lambda },L_{\Lambda }\) and that can change from line to line.
Let us fix \(t \in [0,T]\).
-
Inequality (4.8) of Lemma 4.4 is simply a consequence of the following computation:
$$\begin{aligned} \mathbb E\Big [\Big \vert \tilde{\xi }^{i,N}_{r(t)}-\tilde{\xi }^{i,N}_{t}\Big \vert ^2\Big ]= & {} \mathbb E\left[ \left| \int _{r(t)}^{t}\Phi \Big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )\Big )\,dW_s\right. \right. \\&\left. \left. \; +\int _{r(t)}^{t}g\Big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )\Big )\,ds\right| ^2 \right] \\\le & {} 4\mathbb E\left[ \int _{r(t)}^{t}\Big \vert \Phi \Big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)}\Big )\Big ) - \Phi (r(s),0,0) \Big \vert ^2\,ds\right] \\&\;+\, 4\mathbb E\left[ \int _{r(t)}^{t} \vert \Phi (r(s),0,0) \vert ^2\,ds\right] \\&\; +\, 4(t-r(t))\mathbb E\left[ \int _{r(t)}^{t}\Big \vert g\Big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )\Big ) \right. \\&\left. \;-\, g(r(s),0,0)\vert ^2\,ds \right] \\&\; +\,4(t-r(t))\mathbb E\left[ \int _{r(t)}^{t} \vert g(r(s),0,0) \vert ^2\,ds\right] \\\le & {} 8\big (L_{\Phi }^2+(t-r(t))L_{g}^2\big )\int _{r(t)}^t \mathbb E\Big [\Big \vert \tilde{\xi }^{i,N}_{r(s)} \Big \vert ^2 \Big ] + \mathbb E\Big [\Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big ) \Big \vert ^2 \Big ] ds \\&+ \; 4(t-r(t)) \Big ( \sup _{s \in [0,T]} \vert \Phi (s,0,0) \vert ^2 + (t-r(t)) \sup _{s \in [0,T]} \vert g(s,0,0) \vert ^2 \Big )\\\le & {} C\delta t \ ,\quad \text {as soon as }\quad \delta t \in \, ]0, 1[ \ , \end{aligned}$$where we have used the fact, under items 1. and 6. of Assumption 2, that the second order moment of \(\tilde{\xi }^{i,N}_s\) is uniformly bounded. \(\Lambda \) being uniformly bounded (item 3. of Assumption 2), the function \(\tilde{u}\) as well. We have finally invoked item 6. of Assumption 2.
-
Now, let us focus on the second inequality (4.9) of Lemma 4.4. Note that for any \(y\in \mathbb R^d\), the following inequality holds:
$$\begin{aligned}&\vert \tilde{u}_{r(t)}(y)-\tilde{u}_t(y)\vert \nonumber \\&\quad \le \frac{1}{N} \sum _{i=1}^N \left[ \left| K\Big (y-\tilde{\xi }^{i,N}_{r(t)}\Big ) -K\Big (y-\tilde{\xi }^{i,N}_t\Big )\right| \, e^{\int _0^{r(t)}\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds} \right. \nonumber \\&\qquad + \left. K\Big (y-\tilde{\xi }^{i,N}_t\Big ) \,\left| e^{\int _0^{r(t)}\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds}- e^{\int _0^t\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds} \right| \right] \ . \nonumber \\ \end{aligned}$$(6.5)Using the fact that K and \(\Lambda \) are bounded, one can apply (2.6) to bound the second term of the sum on the r.h.s. of the above inequality as follows:
$$\begin{aligned}&K\Big (y-\tilde{\xi }^{i,N}_t\Big ) \,\left| e^{\int _0^{r(t)}\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\Big )\big )ds}- e^{\int _0^t\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}(\tilde{\xi }^{i,N}_{r(s)})\big )ds}\right| \nonumber \\&\quad \le M_Ke^{tM_{\Lambda }}(t-r(t))M_{\Lambda } \le C\delta t \ . \end{aligned}$$(6.6)The first term of the sum on the r.h.s. of (6.5) is bounded using the Lipschitz property of K and the fact that \(\Lambda \) is bounded.
$$\begin{aligned}&\left| K\Big (y-\tilde{\xi }^{i,N}_{r(t)}\Big ) -K\Big (y-\tilde{\xi }^{i,N}_t\Big )\right| \, e^{\int _0^{r(t)}\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )\big )ds}\nonumber \\&\quad \le L_Ke^{tM_{\Lambda }} \Big \vert \tilde{\xi }^{i,N}_{r(t)}-\tilde{\xi }^{i,N}_t\vert \ . \end{aligned}$$(6.7)Injecting (6.6) and (6.7) in (6.5), for all \(y \in \mathbb R^d\), we obtain
$$\begin{aligned} \vert \tilde{u}_{r(t)}(y) - \tilde{u}_{t}(y) \vert \le C \delta t + \frac{L_Ke^{tM_{\Lambda }}}{N} \sum _{i=1}^N \Big \vert \tilde{\xi }^{i,N}_{r(t)}-\tilde{\xi }^{i,N}_{t} \Big \vert , \end{aligned}$$which finally implies that
$$\begin{aligned} \Vert \tilde{u}_{r(t)}-\tilde{u}_t \Vert _{\infty }^2\le C\delta t ^2+\frac{C}{N}\sum _{i=1}^N \Big \vert \tilde{\xi }^{i,N}_{r(t)}-\tilde{\xi }^{i,N}_t\Big \vert ^2 \ . \end{aligned}$$We conclude by using inequality (4.8) of Lemma 4.4 after taking the expectation of the r.h.s. of the above inequality.
-
Finally, we deal with inequality (4.10) of Lemma 4.4. Observe that the error on the left-hand side can be decomposed as
$$\begin{aligned} \mathbb E\Big [\Big \Vert \tilde{u}_{r(t)}-u_t^{S^N(\tilde{\xi })}\Big \Vert ^2_{\infty }\Big ]\le & {} 2\mathbb E\big [\big \Vert \tilde{u}_{r(t)}-\tilde{u}_t\big \Vert ^2_{\infty }\big ]+2\mathbb E\Big [\Big \Vert \tilde{u}_{t}-u_t^{S^N(\tilde{\xi })}\Big \Vert ^2_{\infty }\Big ] \nonumber \\\le & {} C\delta t +2\mathbb E\Big [\Big \Vert \tilde{u}_{t}-u_t^{S^N(\tilde{\xi })}\Big \Vert ^2_{\infty }\Big ]\ , \end{aligned}$$(6.8)where we have used inequality (4.9) of Lemma 4.4.
Let us consider the second term on the r.h.s. of the above inequality. To simplify the notations, we introduce the real valued random variables
$$\begin{aligned} V_t^i := e^{\int _0^t\Lambda \big (s,\tilde{\xi }^{i,N}_{s},u^{S^N(\tilde{\xi })}_{s}\big (\tilde{\xi }^{i,N}_{s}\big )\big )ds}\quad \text {and}\quad \tilde{V}_t^i := e^{\int _0^t\Lambda \big (r(s),\tilde{\xi }^{i,N}_{r(s)},\tilde{u}_{r(s)}\big (\tilde{\xi }^{i,N}_{r(s)}\big )\big )ds}\ ,\nonumber \\ \end{aligned}$$(6.9)defined for any \(i=1, \ldots N\) and \(t\in [0,T]\).
Using successively inequalities (6.1) of Lemma 5.1, (4.8) of Lemma 4.4 and (2.9) of Proposition 2.5, we have for all \(i \in \{1, \ldots ,N\}\),
$$\begin{aligned} \mathbb E\big [\big \vert \tilde{V}_t^i-V_t^i \big \vert ^2\big ]\le & {} C\delta t + C \mathbb E\left[ \int _0^t \Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_s\Big )\Big \vert ^2 ds \right] \nonumber \\\le & {} C\delta t + C \mathbb E\left[ \int _0^t \Big \vert \tilde{u}_{r(s)}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )\Big \vert ^2 ds \right] \nonumber \\&+ \; C \mathbb E\left[ \int _0^t \Big \vert u_{s}^{S^N(\tilde{\xi })}\Big (\tilde{\xi }^{i,N}_{r(s)}\Big )-u^{S^N(\tilde{\xi })}_s\Big (\tilde{\xi }^{i,N}_{s}\Big )\Big \vert ^2 ds \right] \nonumber \\\le & {} C\delta t +C\int _0^t \left[ \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] + \mathbb E\Big [\Big \vert \tilde{\xi }^{i,N}_{r(s)}-\tilde{\xi }^{i,N}_s\Big \vert ^2\Big ] \right] \, ds \nonumber \\\le & {} C\delta t +C\int _0^t \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] \, ds \ . \end{aligned}$$(6.10)On the other hand, inequality (6.2) of Lemma 5.1 implies
$$\begin{aligned} \Big \Vert \tilde{u}_{t}-u_t^{S^N(\tilde{\xi })} \Big \Vert _{\infty }^2 \le \frac{M_K^2}{N}\sum _{i=1}^N \big \vert \tilde{V}_t^i-V_t^i \big \vert ^2 \ . \end{aligned}$$(6.11)Taking the expectation in both sides of (6.11) and using (6.10) give
$$\begin{aligned} \mathbb E\Big [\Big \Vert \tilde{u}_{t}-u_t^{S^N(\tilde{\xi })}\Big \Vert ^2_{\infty }\Big ]\le & {} \frac{M_K^2}{N}\sum _{i=1}^N \mathbb E\left[ \big \vert \tilde{V}_t^i-V_t^i \big \vert ^2 \right] \le C\delta t\nonumber \\&+\,C\int _0^t \mathbb E\Big [\Big \Vert \tilde{u}_{r(s)}-u^{S^N(\tilde{\xi })}_s\Big \Vert _\infty ^2\Big ] \, ds\ . \end{aligned}$$(6.12)We end the proof by injecting this last inequality in (6.8) and by applying Gronwall’s lemma.\(\square \)
Rights and permissions
About this article
Cite this article
Le Cavil, A., Oudjane, N. & Russo, F. Particle system algorithm and chaos propagation related to non-conservative McKean type stochastic differential equations. Stoch PDE: Anal Comp 5, 1–37 (2017). https://doi.org/10.1007/s40072-016-0079-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40072-016-0079-9
Keywords
- Chaos propagation
- Nonlinear Partial Differential Equations
- McKean type NonLinear Stochastic Differential Equation
- Particle systems
- Probabilistic representation of PDEs