Walk-on-Spheres Monte Carlo and deep neural network approximations of elliptic PDEs with drift and killing

Walk-on-Spheres Monte Carlo and deep neural network approximations of elliptic PDEs with drift and killing Konrad Kleinberg1 , Thomas Kruse2 1 Department of Mathematics & Informatics, University of Wuppertal,

arXiv:2608.09494v1 [math.NA] 10 Aug 2026

a Germany; e-mail: kleinberg○uni-wuppertal.de 2 Department of Mathematics & Informatics, University of Wuppertal,

a Germany; e-mail: tkruse○uni-wuppertal.de

August 11, 2026 Abstract In this paper we provide Monte Carlo and deep neural network approximations for stochastic representations of solutions to linear elliptic partial differential equations with constant diffusion, drift and killing. Building on the modified Walk-onSpheres algorithm of Beznea et al. (arXiv:2209.01432), we introduce Monte Carlo estimators that explicitly incorporate sampled random times arising in the analyzed stochastic representations. We establish uniform error bounds for these estimators and show that, under suitable assumptions, a prescribed approximation accuracy is achieved with sample complexities growing at most polynomially in both the inverse accuracy and the problem dimension. Furthermore, we prove a deep neural network approximation result for the stochastic representations. Assuming suitable neural network representations of the boundary data and the distance function to the boundary, we use the constructed Monte Carlo to design deep neural networks that approximate the representation uniformly with a number of parameters growing at most polynomially in the inverse accuracy and the problem dimension. These results extend previous complexity analyses to a broader class of elliptic equations involving drift and killing.

1

Introduction & Problem formulation

In this work, we consider the approximation of functions w : D → R, Z τ x  x w(x) = E[h0 (τ , x + Bτ x )] + E h1 (s, x + Bs ) ds , x ∈ D,

(1)

0

where d ∈ N = {1, 2, . . .}, D ⊆ Rd is open, bounded, and convex, h0 , h1 : [0, ∞) × D → R are bounded and Lipschitz continuous, (Ω, F, P) is a probability space on which all appearing random variables are defined, B = (Bt )t∈[0,∞) : Ω × [0, ∞) → Rd is a ddimensional standard Brownian motion starting in 0, and τ x , x ∈ D, is the first exit time 1

of the process x + B from D, i.e., τ x = inf{t ∈ [0, ∞) : x + Bt ∈ ∂D}, x ∈ D. The approximation of expectations of the form (1) is particularly relevant in the numerical solution of partial differential equations (PDEs). Indeed, such representations appear naturally in stochastic representations of solutions of linear elliptic drift-diffusion PDEs on bounded domains of the following type: 1 tr(σσ ⊤ D2 u) + ⟨b, ∇u⟩ − ru + f = 0 2 u ∂D = g

on D,

(2)

on ∂D,

where u : D → R is the unknown, σ ∈ Rd×d , b ∈ Rd , r ∈ [0, ∞), f : D → R, and g : ∂D → R (see Section 2 for a precise derivation of the relation between (1) and (2)). The goal of this work is to develop Monte Carlo schemes with error and complexity analyses as well as artificial neural network (ANN) approximations for expectations of the form (1), with a particular focus on high-dimensional situations. Probabilistic approximation methods for elliptic boundary problems include in particular the so called Walk-on-Spheres algorithm, originally proposed in [23] to √ approximate the solution of the Dirichlet problem (i.e., the special case of (2) with σ = 2 IdRd , b = 0, r = 0, f = 0) given by ∆u = 0

on D,

u ∂D = g

on ∂D,

(3)

via Monte Carlo simulation. In particular, it allows to efficiently approximate the exit point of Brownian motion from a bounded domain. Conceptually the Walk-on-Spheres algorithm works as follows: At the current position x ∈ D determine the largest sphere around x contained in D. To obtain the next position, sample uniformly from this sphere. The key observation here is that this new random position is indeed identically distributed to the location of first exit of a Brownian motion started in x from said sphere. To obtain an approximation for the exit point of Brownian motion from the entire domain, this procedure is repeated until the process is within a prescribed distance to the boundary of the domain. In particular, the number of steps required to reach that location is in general random. In this original algorithm the spheres from which the next point of the process is sampled exhibit maximal radii, i.e., the radius of the sphere to be sampled from is given by the distance of the current position to the boundary of the domain. Subsequent developments based on this algorithm cover methods for more general elliptic boundary value problems (see, e.g., [7, 21, 33]). Recently, there is also a growing interest in Monte Carlo approximations of elliptic PDEs that include a drift component. Indeed, in the work [30] the Walk-on-Spheres algorithm is extended to elliptic drift-diffusion equations by utilizing a von Mises-Fisher exit distribution on the successive spheres. The article [31] introduces a Monte Carlo method for self-adjoint elliptic PDEs with constant coefficients that estimates the solutions and its derivatives at multiple points from one ensemble of trajectories. In [32], the authors extend this global approach to elliptic drift-diffusion equations. To obtain global approximations for the drift-free Poisson problem (i.e., the special case of (2) with σ = IdRd , b = 0, r = 0) 1 ∆u + f = 0 2 u ∂D = g 2

on D, on ∂D,

(4)

the works [11] and [6] combine Walk-on-Spheres based Monte Carlo estimators with suitable neural networks representations and approximations. In particular, under suitable assumptions these works construct ANNs that approximate the solution of (4) with a complexity that only grows polynomially in both the inverse of the approximation accuracy1 and the problem dimension, thereby mitigating the so-called curse of dimensionality. The general strategy of combining compositional and approximation properties of ANNs with Monte Carlo methods to overcome the curse of dimensionality was first developed for parabolic linear PDEs (see, e.g., [5,12,18]). It was subsequently extended to nonlinear equations (see, e.g., [1, 2, 8, 15, 25, 26, 27])2 . Moreover, this approach was used, for example, in the context of two-player zero-sum stochastic differential games (see, e.g., [29]) and Markov decision processes (see, e.g., [4] and [16]). Two features of the framework developed in [6] are particularly important for our work. First, it employs a modified version of the Walk-on-Spheres process utilizing a specific class of modified distance functions as a substitute for the true distance function in order to determine the radii of the successive spheres from which the successive positions are sampled. Second, the framework admits a deterministic stopping criterion, independent of the starting point of the Walk-on-Spheres process, in place of the random number of steps used in the classical Walk-on-Spheres algorithm. Both, the deterministic stopping rule and the modified distance functions play an important role in the construction of the ANN approximations. Furthermore, the authors of [6] work under exterior ball condition on D rather than assuming convexity of D. Building on this framework, we analyze in the present work Monte Carlo estimators for expectations of the form (1) and consequently of solutions of elliptic drift-diffusion equations of the form (2). More precisely, we consider Monte Carlo estimators w̄ : D×Ω → R satisfying for x ∈ D that  n  M
1X 1P x,i x,i 2 x,i x,i x,i 2 i x,i x,i i h0 (τ̄M , X̄M ) + r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk . w̄(x) = n i=1 d k=1 (5) Here, the number n ∈ N denotes the number of sample paths of the Walk-on-Spheres process, the number M ∈ N denotes the deterministic number of steps the employed Walk-on-Spheres process undertakes, the function r̄ : D → R determines the radii of the successive spheres in the generation of the Walk-on-Spheres process and is to be understood as a suitable substitute for the true distance to the boundary of D. For the x,i sample with index i ∈ {1, . . . , n} the random variables X̄0x,i , . . . , X̄M denote the M steps of the Walk-on-Spheres process with start in X̄0x,i = x ∈ D. The random variable τ̄kx,i x,i correspond to the physical time a Brownian motion started in the position X̄k−1 needs to x,i x,i hit the boundary of the sphere with radius r̄(X̄k−1 ) around X̄k−1 . The random variable (Vki , Yki ) correspond to the time and space occupation of a Brownian motion with start in 0 inside the unit sphere. The estimator in (5) extends the estimator introduced in [6] by incorporating the samx,i pled random times τ̄M , x ∈ D, M ∈ N, i ∈ {1, . . . , n}. This additional time dependency appears in stochastic representations of solutions of (2) as a compensation for the drift b and killing r components (see Proposition 2.2 and Remark 2.3 and below). 1 2

The approximation error is measured in L2 (D) in [11] and in L∞ (D)in [6]. See also [3] for a survey on deep-learning based approximation methods for PDEs.

3

We next briefly describe the two main contributions of this article. To characterize appearing complexities (e.g., sample complexity, number of parameters describing an ANN), we adopt the following terminology: A real number c ∈ R is called an absolute constant, if c does not depend on any variables or parameters in the problem. Moreover, for quantities Q, q1 , . . . , qn ∈ R, where n ∈ N, we say that Q depends only on q1 , . . . , qn if Q is an explicit function of the variables q1 , . . . , qn and Q has no other dependencies. In this case, this dependency is at most polynomial if there exists an absolute constant c ∈ [0, ∞) such that Q ≤ c(1 + |q1 | + · · · + |qn |)c . First, we establish an error analysis for Monte Carlo approximations (5) for expectations of the form (1) in the L∞ -sense (see Theorem 4.9 and Corollary 4.10 below). In particular, we demonstrate that for a prescribed approximation accuracy ε ∈ (0, 1) the estimator (5) achieves E[supx∈D |w(x)− w̄(x)|] ≤ ε under suitable assumptions on the modified distance function r̄ as well as with suitable choices of n, M ∈ N. More specifically, n and M can be chosen such that max{n, M } ≤ cε−q , where q ∈ [0, ∞) is an absolute constant and c ∈ [0, ∞) is a constant that depends only on sup(t,x)∈[0,∞)×D |hi (t, x)|, i ∈ {1, 2}, the Lipschitz constants of hi , i ∈ {1, 2}, the Lipschitz constant as well as a nondegeneracy constant3 of the modified distance r̄, the diameter diam(D) of the domain, and the dimension d and this dependency is at most polynomial. In particular, imposing that these problem features grow at most polynomially with respect to the dimension d the Monte Carlo scheme indeed overcomes the curse of dimensionality. Second, we establish in Theorem 5.6 an ANN approximation result for functions w : D → R, w(x) = E[h0 (τ x , x + Bτ x )] (i.e., (1) in the special case h1 ≡ 0). In particular, under the assumption that h0 can be represented by an ANN and the distance to the boundary dist(·, ∂D) can be suitably approximated by an ANN then w can be approximated in the L∞ -sense with accuracy ε ∈ (0, 1) by an ANN Ψ such that the number of parameters of Ψ is bounded by c̄ε−q̄ , where q̄ ∈ [0, ∞) is an absolute constant and c̄ ∈ [0, ∞) depends only on the number of parameters, the Lipschitz constant, and the least upper bound on [0, ∞) × D of the ANN representing h0 , the number of parameters and a uniform Lipschitz constant of the ANNs approximating the distance to the boundary, diam(D), and d and this dependendy is at most polynomial. In particular, under similar assumptions as for the Monte Carlo estimator, a curse of dimensionality relief is obtained (see Remark 5.7 below). The remainder of this article is structured as follows. In Section 2 below we establish the connection between functions of the form (1) and solutions of the PDE (2). In Section 3 we introduce the modified Walk-on-Spheres process and some of its important distributional properties and we present a Walk-on-Spheres-based representation of the expectation (1). In Section 4 we present the Monte Carlo estimator based on the Walkon-Spheres process established in Section 3 and provide an error analysis. In Section 5 we derive ANN approximation results for expectations of the form (1) utilizing the error analysis established in Section 4.

2

A Girsanov-based Feynman-Kac representation

In this section, we establish the connection between expectations of the form (1) and classical solutions of the PDE (2) via suitable stochastic representations. 3

For details, see Definition 3.3 and Corollary 4.10 below

4

Unless otherwise specified, let d ∈ N, σ ∈ Rd×d , b ∈ Rd , r ∈ R, D ⊆ Rd , let f : D → R, g : ∂D → R. In the following remark, we recall sufficient conditions to establish existence and uniqueness of a classical solution of the PDE (2) (see, e.g., [10, Chapter 6, Theorem 6.13], [9, Chapter 6, Theorem 2.4]). Remark 2.1. Assume σ is invertible, assume r ≥ 0, assume that D ⊆ Rd is open, connected, bounded, and satisfies an exterior ball condition at every boundary point, assume that f is uniformly α-Hölder continuous, for some α ∈ (0, 1), and assume that g is continuous on ∂D. Then there exists a unique u ∈ C 0 (D) ∩ C 2 (D) that satisfies (2). The next Proposition 2.2 gives rise to a stochastic representation of the solution of (2) that is the base for the Monte Carlo estimates employed in subsequent section. We fix some more notation. Unless otherwise specified, let (Ω, F, P) be a probability space, let B : [0, ∞) × Ω → Rd be a standard Brownian motion, and let (Ft )t∈[0,∞) be the completed filtration generated by B. For every x ∈ D let τ x = inf{t ∈ [0, ∞) : x + σBt ∈ ∂D}.

(6)

Proposition 2.2. Assume that D is open, bounded, and connected, that f and g are continuous, that σ is invertible, and that r ≥ − 21 ∥σ −1 b∥2 . Let u ∈ C 0 (D) ∩ C 2 (D) be a solution of (2). Then it holds for all x ∈ D that  1 −1 2 x −1 u(x) = E e−(r+ 2 ∥σ b∥ )τ +⟨σ b,Bτ x ⟩ g(x + σBτ x )  Z τx −(r+ 21 ∥σ −1 b∥2 )s+⟨σ −1 b,Bs ⟩ e + f (x + σBs ) ds . (7) 0

Proof. Let x ∈ D. Note that Itô’s formula implies for all t ∈ [0, ∞) that 1

de−(r+ 2 ∥σ

−1 b∥2 )(t∧τ x )+⟨σ −1 b,B

t∧τ x ⟩

1

= 1{t<τ x } e−(r+ 2 ∥σ

−1 b∥2 )t+⟨σ −1 b,B ⟩ t

−r dt + ⟨σ −1 b, dBt ⟩ (8)

and du(x + σBt∧τ x ) = 1{t<τ x } ⟨∇u(x + σBt ), σ dBt ⟩ +

1 tr(σσ ⊤ D2 u(x + σBt )) dt . 2

(9)

Combining this, the fact that for all t ∈ [0, ∞) it holds that Bt∧τ x 1{t<τ x } = Bt 1{t<τ x } , and the fact that u solves (2) with the product rule entails for all t ∈ [0, ∞) that   −(r+ 12 ∥σ −1 b∥2 )(t∧τ x )+⟨σ −1 b,Bt∧τ x ⟩ x d e u(x + σBt∧τ )  1 −1 2 −1 = 1{t<τ x } e−(r+ 2 ∥σ b∥ )t+⟨σ b,Bt ⟩ ⟨∇u(x + σBt ), σ dBt ⟩ − f (x + σBt ) dt − ⟨b, ∇u(x + σBt )⟩ dt + ru(x + σBt ) dt − ru(x + σBt ) dt + ⟨b, ∇u(x + σBt )⟩ dt  (10) + u(x + σBt )⟨σ −1 b, dBt ⟩  1 −1 2 −1 = 1{t<τ x } e−(r+ 2 ∥σ b∥ )t+⟨σ b,Bt ⟩ ⟨σ ⊤ ∇u(x + σBt ) + σ −1 bu(x + σBt ), dBt ⟩  − f (x + σBt ) dt .

5

Written as integrals it holds for all t ∈ [0, ∞) that 1

−1

2

−1

x

e−(r+ 2 ∥σ b∥ )(t∧τ )+⟨σ b,Bt∧τ x ⟩ u(x + σBt∧τ x ) − u(x) Z t∧τ x 1 −1 2 −1 =− e−(r+ 2 ∥σ b∥ )s+⟨σ b,Bs ⟩ f (x + σBs ) ds 0 Z t∧τ x 1 −1 2 −1 e−(r+ 2 ∥σ b∥ )s+⟨σ b,Bs ⟩ ⟨u(x + σBs )σ −1 b + σ ⊤ ∇u(x + σBs ), dBs ⟩. +

(11)

0

let τk , k ∈ N, be a localizing sequence of stopping times for the local martingale RNext, ·∧τ x −(r+ 1 ∥σ −1 b∥2 )t+⟨σ −1 b,Bt ⟩ 2 e ⟨u(x + σBt )σ −1 b + σ ⊤ ∇u(x + σBt ), dBt ⟩. This ensures for all 0 t ∈ [0, ∞), k ∈ N that  1 −1 2 x −1 u(x) = E e−(r+ 2 ∥σ b∥ )(t∧τk ∧τ )+⟨σ b,Bt∧τk ∧τ x ⟩ u(x + σBt∧τk ∧τ x )  Z t∧τk ∧τ x −(r+ 21 ∥σ −1 b∥2 )s+⟨σ −1 b,Bs ⟩ f (x + σBs ) ds . (12) + e 0

This, the dominated convergence theorem, and the fact that u ∂D = g on ∂D demonstrate that  1 −1 2 x −1 u(x) = lim E e−(r+ 2 ∥σ b∥ )(t∧τk ∧τ )+⟨σ b,Bt∧τk ∧τ x ⟩ u(x + σBt∧τk ∧τ x ) t→∞ k→∞

 Z t∧τk ∧τ x −(r+ 12 ∥σ −1 b∥2 )s+⟨σ −1 b,Bs ⟩ + e f (x + σBs ) ds 0  1 −1 2 x −1 = E e−(r+ 2 ∥σ b∥ )τ +⟨σ b,Bτ x ⟩ u(x + σBτ x )  Z τx −(r+ 12 ∥σ −1 b∥2 )s+⟨σ −1 b,Bs ⟩ e f (x + σBs ) ds + 0  1 −1 2 x −1 = E e−(r+ 2 ∥σ b∥ )τ +⟨σ b,Bτ x ⟩ g(x + σBτ x )  Z τx −(r+ 12 ∥σ −1 b∥2 )s+⟨σ −1 b,Bs ⟩ e f (x + σBs ) ds . +

(13)

0

This completes the proof. In the following remark, we informally derive another stochastic representation of the solution u of (2) based on the Feynman-Kac representation and establish a connection to the representation (7) as well as reason why the representation (7) is preferable for our work. Remark 2.3. Let W : [0, ∞) × Ω → Rd be a standard Brownian motion on Ω under the probability measure Q. For every x ∈ Rd let X x : [0, ∞) × Ω → Rd and τ̃ x : Ω → [0, ∞) satisfy Xtx = x + bt + σWt , t ∈ [0, ∞), and τ̃ x = inf{t ∈ [0, ∞)|Xtx ∈ ∂D}. Then the Feynman-Kac formula yields under appropriate assumptions for every x ∈ Rd that   Z τ̃ x Q −rτ̃ x x −rs x u(x) = E e g(Xτ̃ x ) + e f (Xs ) ds . (14) 0

6

In Section 3 and following, we employ the Walk-on-Spheres algorithm which is based on the isotropy of Brownian motion. For this reason, representation (7), which employs exit times of x + σB, is more convenient than (14) which is based on the non-isotropic process X x. Note that (7) can be derived from (14) via Girsanov’s theorem (see, e.g., [34, Appendix A.1] for a similar derivation). To this end, let K : [0, ∞)×Ω → Rd , L : [0, ∞)×Ω → R, and τKx : Ω → [0, ∞], x ∈ Rd , satisfy Kt = Wt + σ −1 bt, Lt = e

t ∈ [0, ∞),

−⟨σ −1 b,Wt ⟩− 21 ∥σ −1 b∥2 t

,

t ∈ [0, ∞),

τKx = inf{t ∈ [0, ∞) : x + σKt ∈ ∂D},

(15) d

x∈R . −1

1

−1

2

Note that for all t ∈ [0, ∞), x ∈ Rd we have Xtx = x + σKt , Lt = e−⟨σ b,Kt ⟩+ 2 ∥σ b∥ t , and τ̃ x = τKx . Then, Girsanov’s theorem (see, e.g., [19, Section 3.5, Theorem 5.1]) implies for T = LT . every T ∈ [0, ∞) that K is a Brownian motion on (Ω, FT , (Ft )t∈[0,T ] , PT ) with dP dQ By a suitable limiting procedure we obtain a measure P∞ such that K is a Brownian motion under P∞ and it follows from (14) that for all x ∈ Rd it holds that  x +⟨σ −1 b,K x ⟩ −(r+ 21 ∥σ −1 b∥2 )τK P∞ τ K g(x + σK x ) u(x) = E e τK  Z τKx −(r+ 12 ∥σ −1 b∥2 )s+⟨σ −1 b,Ks ⟩ f (x + σKs ) ds . (16) e + 0

This exactly corresponds to (7). Remark 2.4. Under the assumption that σ is invertible one can transform the elliptic PDE (2) to one with isotropic Laplacian. Indeed, let v ∈ C 2 (σ −1 D) satisfy 1 ∆v + ⟨σ −1 b, ∇v⟩ − rv + f (σ·) = 0 on σ −1 D 2 v ∂(σ−1 D) = g(σ·) on ∂(σ −1 D).

(17)

Then the function u(x) = v(σ −1 x), x ∈ D, satisfies u ∈ C 2 (D) and (2). For this reason we focus attention on the case σ = Id in the remainder of this article. A proof for this transformation in the case b = 0, r = 0 is given in [6, Lemma 2.1]. Remark 2.5. In the situation of Proposition 2.2 with σ = Id let h0 : [0, ∞) × ∂D → R, h1 : [0, ∞) × D → R satisfy for all t ∈ [0, ∞), x ∈ ∂D, y ∈ D that 1

2

h0 (t, x) = e−(r+ 2 ∥b∥ )t+⟨b,x⟩ g(x)

and

1

2

h1 (t, y) = e−(r+ 2 ∥b∥ )t+⟨b,y⟩ f (y).

Then it holds for all x ∈ D that  Z τ x  −⟨b,x⟩ x u(x) = e E[h0 (τ , x + Bτ x )] + E h1 (s, x + Bs ) ds .

(18)

(19)

0

Under the additional assumption that g is extendable to D and that both g and f are Lipschitz on D, it holds that h0 as in (18) is well-defined on [0, ∞) × D and h0 and h1 are bounded and Lipschitz continuous. Hence, the relation between the PDE solution u and the expectation w as in (1) is established as u(x) = e−⟨b,x⟩ w(x) for x ∈ D. We remark that this transformation is also used in [30, Section 2]. 7

3

A modified Walk-on-Spheres algorithm

In this section, we introduce the modified Walk-on-Spheres algorithm as proposed in [6] and demonstrate some relevant distributional properties. In particular, we present in Lemma 3.7 estimates on the tail probability of the number of steps the Walk-onSpheres process requires to reach the boundary of the domain within a certain distance. Moreover, we establish in Lemma 3.9 a representation of functions of the form (1) based on the established Walk-on-Spheres process which subsequently motivates the Monte Carlo estimator considered in Section 4. The following lemma demonstrates a consequence of the rotational invariance of Brownian motion. Lemma 3.1. Let τ = inf{t ∈ [0, ∞) : ∥Bt ∥ ≥ 1}. Then it holds that τ and Bτ are independent. Proof. Throughout this proof let S = {y ∈ Rd : ∥y∥ = 1} and let µ : B(S) → [0, 1] denote the uniform distribution on (S, B(S)). First, observe that τ and Bτ are measurable path functionals of the path of B. Next, note that the fact that for all R ∈ SO(d) it holds that B and RB are identically distributed and the fact that for all R ∈ SO(d), x ∈ Rd it holds that ∥Rx∥ = ∥x∥ yield for all R ∈ SO(d) that (τ, Bτ ) and (τ, RBτ ) are identically distributed. Moreover, observe that the fact that [0, ∞] is a Polish space ensures that there exists a regular conditional distribution κ : [0, ∞] × B(S) → [0, 1] of Bτ given τ (cf., [20, Section 8.3]). This implies for all A ∈ B([0, ∞]), C ∈ B(S) that      P[τ ∈ A, Bτ ∈ C] = E 1{τ ∈A} 1{Bτ ∈C} = E 1{τ ∈A} E 1{Bτ ∈C} | τ Z Z   (20) = E 1{Bτ ∈C} | τ 1{τ ∈A} dP = κ(t, C)(P ◦ τ −1 )(dt). Ω

A

Combining this with the fact that for all R ∈ SO(d) it holds that (τ, Bτ ) and (τ, RBτ ) are identically distributed demonstrates for all A ∈ B([0, ∞]), C ∈ B(S), R ∈ SO(d) that Z κ(t, C)(P ◦ τ −1 )(dt) = P[τ ∈ A, Bτ ∈ C] = P[τ ∈ A, RBτ ∈ C] A Z (21) ⊤ −1 = κ(t, R C)(P ◦ τ )(dt). A

This implies that for P ◦ τ −1 -a.a. t ∈ [0, ∞) it holds that κ(t, ·) is a rotational invariant probability measure on S. This and the fact that µ is the unique rotationally invariant probability measure on S (cf., [22, Theorem 3.4]) imply that for P ◦ τ −1 -a.a. t ∈ [0, ∞) it holds that κ(t, ·) = µ. This and (20) yield for all A ∈ B([0, ∞]), C ∈ B(S) that P[τ ∈ A, Bτ ∈ C] = P[τ ∈ A]µ(C).

(22)

This shows that τ and Bτ are independent. The proof of Lemma 3.1 is thus complete. Throughout the remainder of this section, assume that D is open and bounded. Let r : Rd → [0, ∞) satisfy for all x ∈ Rd that r(x) = inf{∥x − y∥ : y ∈ ∂D}.

(23)

The following lemma is a modification of [11, Lemma 3.2]. The geometric proof given there can be adapted to yield the following statement. Recall for all x ∈ D that τ x = inf{t ∈ [0, ∞) : x + Bt ∈ ∂D}. 8

Lemma 3.2. Assume that D is convex. Then it holds for all x ∈ D that E[τ x ] ≤ r(x) diam(D).

(24)

The next definition is [6, Definition 2.7] and describes the class of modified distance functions, which subsequently determines the radii of the successive spheres on which the Walk-on-Spheres process is defined. Definition 3.3. Let β ∈ (0, 1], ε ∈ [0, ∞), let r̃ : D → [0, ∞) be Lipschitz continuous, and assume for all x, y ∈ D with r(x) ≥ ε that r̃(y) ≤ r(y) and r̃(x) ≥ βr(x). Then r̃ is called (β, ε)-distance on D. With this notion of modified distance functions, we now introduce the Walk-on-Spheres process. Let β ∈ (0, 1], δ ∈ [0, ∞), let r̄ be a (β, δ)-distance on D. Let τkx : Ω → [0, ∞), k ∈ N0 , satisfy for all x ∈ D, k ∈ N that τ0x = 0 and x x x τkx = inf{s ∈ [τk−1 , ∞) : ∥Bs − Bτk−1 ∥ ≥ r̄(x + Bτk−1 )},

(25)

let Zkj : Ω → Rd , j, k ∈ N, be standard normally distributed, let ξkj : Ω → Rd , j, k ∈ N, satisfy for all j, k ∈ N that ξkj = ∥Zkj ∥−1 Zkj , let X̄kx,j : Ω → D, x ∈ D, j ∈ N, k ∈ N0 , satisfy for all x ∈ D, j, k ∈ N that X̄0x,j = x and x,j x,j X̄kx,j = X̄k−1 + r̄(X̄k−1 )ξkj ,

(26)

let ζ : Ω → [0, ∞) satisfy ζ = inf{t ∈ [0, ∞) : ∥Bt ∥ ≥ 1}, let ρjk , k, j ∈ N, be i.i.d. copies of ζ, assume that ρjk , Zkj , j, k ∈ N are independent, let τ̄kx,j : Ω → [0, ∞), j ∈ N, k ∈ N0 satisfy for all x ∈ D, j, k ∈ N that τ̄0x,j = 0 and x,j x,j τ̄kx,j = τ̄k−1 + r̄2 (X̄k−1 )ρjk .

(27)

Lemma 3.4. For all x ∈ D, k ∈ N0 , j ∈ N it holds that (τ̄kx,j , X̄kx,j ) and (τkx , x + Bτkx ) are identically distributed. Proof. First, note that (τ̄0x,j , X̄0x,j ) = (0, x) = (τ0x , x + Bτ0x ). Next, observe that by assumption it holds that τ̄1x,j = r̄2 (x)ρj1 and X̄1x,j = x + r̄(x)ξ1j are independent. Moreover, note that Lemma 3.1 proves that τ1x and x + Bτ1x are independent. Combining this, the fact that τ1x and τ̄1x,j are identically distributed, and the fact that x + Bτ1x and X̄1x,j are identically distributed yields that (τ̄1x,j , X̄1x,j ) and (τ1x , x + Bτ1x ) are identically distributed. This, the strong Markov property (cf., [19, Chapter 2.6]), and induction complete the proof of Lemma 3.4. For every ε ∈ (0, ∞) let Dε = {x ∈ D : r(x) ≥ ε}.

(28)

For every ε ∈ (0, ∞), x ∈ D, j ∈ N let kεx = inf{k ∈ N0 : x + Bτkx ∈ / Dε },

(29)

k̄εx,j = inf{k ∈ N0 : X̄kx,j ∈ / Dε },

(30)

Lemma 3.5. For all ε ∈ (0, ∞), x ∈ D it holds that kεx and k̄εx,1 are identically distributed. 9

Proof. The strong Markov property (cf., [19, Section 2.6]) and the assumption that ρjk , Zkj , j, k ∈ N are independent ensure for all x ∈ D that (X̄kx,1 )k∈N0 and (x + Bτkx )k∈N0 are identically distributed. This implies for all ε ∈ (0, ∞), x ∈ D that kεx and k̄εx,1 are identically distributed. This completes the proof of Lemma 3.5. The combination of the next two lemmas quantifies the decay of the tail probabilities of k̄δx,1 the number of steps the Walk-on-Spheres algorithm needs to reach regions of the domain close to the boundary. To this end Lemma 3.6 provides bounds for the moment generating function of a Brownian motions first exit from a sphere and Lemma 3.7 establishes the estimates of the tail probabilities of k̄δx,1 . The statements are modifications of [6, Proposition 2.11]. We provide proofs for the convenience of the reader. Lemma 3.6. Let r ∈ (0, ∞), γ ∈ (0, rd2 ) and let τ = inf{t ∈ [0, ∞) : ∥Bt ∥ = r}, Then it holds that γr2 1 1+ ≤ E[eγτ ] ≤ (31) 2 . d 1 − γr d

Proof. Throughout this proof let v, w : Rd → R satisfy for all x ∈ Rd that v(x) =

1 γ∥x∥2 − 2 2d

and

w(x) = 1 −

γ∥x∥2 . d + γr2

Itô’s formula yields for every h ∈ {v, w}, t ∈ [0, ∞) that Z t Z t 1 γs γt e (γh(Bs ) + ∆h(Bs )) ds + e h(Bt ) = h(0) + eγs ⟨∇h(Bs ), dBs ⟩. 2 0 0

(32)

(33)

For every h R∈ {v, w} let τkh , k ∈ N, be a localizing sequence of stopping times for the local · martingale 0 eγs ⟨∇h(Bs ), dBs ⟩ and for every h ∈ {v, w}, k ∈ N let Tkh : Ω → R satisfy Tkh = k ∧τ ∧τkh . Combining the fact that for all h ∈ {v, w}, k ∈ NR it holds that Tkh ≤ k ∧τ , · the fact that for all h ∈ {v, w} it holds that (τkh )k∈N localizes 0 eγs ⟨∇h(Bs ), dBs ⟩, and the optional stopping theorem with (33) establishes for all h ∈ {v, w}, k ∈ N that Z Tk   γT  1 γs k (34) E e h(BTk ) = h(0) + E e (γh(Bs ) + ∆h(Bs )) ds . 2 0 Furthermore, note that the fact that for every h ∈ {v, w} it holds that P(limk→∞ τkh = ∞) = 1 ensures for every h ∈ {v, w} that P(limk→∞ Tkh = τ ) = 1. This and the fact that P(τ < ∞) = 1 (cf. e.g., [19, Section 4.2], [24, Lemma 4.27]) imply for every h ∈ {v, w} that   h P lim eγTk h(BTkh ) = eγτ h(Bτ ) = 1. (35) k→∞

Moreover, observe that the facts that γr2 < d and that for all k ∈ N it holds that Tkv ≤ τ v assure for all k ∈ N that eγTk v(BTkv ) ≥ 0. This, the fact that for all x ∈ Rd it holds that 2

2

2

∥x∥ γv(x) + 21 ∆v(x) = − γ 2d ≤ 0, the fact that v(Bτ ) = 12 − γr > 0, the fact that for all 2d v k ∈ N it holds that Tk ≤ τ , (34), (35), and Fatou’s lemma demonstrate that    v  1 γr2 1 γτ E[e ] − = E[eγτ v(Bτ )] ≤ lim inf E eγTk v(BTkv ) ≤ v(0) = . (36) k→∞ 2 2d 2

10

Hence, it holds that 1

E[eγτ ] ≤

2

1 − γrd

.

(37)

Next, note that the fact that for all x ∈ Rd it holds that w(x) ≤ 1. Combining this with the fact that it holds for all k ∈ N that Tkw ≤ τ assures that for all k ∈ N it holds w that eγTk w(BTkw ) ≤ eγτ . This, the fact that for all x ∈ Rd with ∥x∥ ≤ r it holds that 2

2

2

2

−∥x∥ ) γr ≥ 0, the fact that w(Bτ ) = 1 − d+γr γw(x) + 21 ∆w(x) = γ (rd+γr 2 2 > 0, (34), (35), (37), and the dominated convergence theorem yield that   γr2 w γτ = E[eγτ w(Bτ )] = lim E[eγTk w(BTkw )] ≥ w(0) = 1. (38) E[e ] 1 − 2 k→∞ d + γr

This demonstrates E[eγτ ] ≥

1 γr2

1 − d+γr2

=

d + γr2 γr2 =1+ . d d

(39)

This and (37) establish (31). This completes the proof of Lemma 3.6. Lemma 3.7. Assume δ > 0. Then it holds for all M ∈ N, x ∈ D that −M 
β 2 δ2 P k̄δx,1 ≥ M ≤ 2 1 + 2 diam(D) . 2

(40)

Proof. Throughout this proof let Tc : Ω → [0, ∞], c ∈ (0, ∞), satisfy for every c ∈ (0, ∞) d that Tc = inf{t ∈ [0, ∞) : ∥Bt ∥ = c} and let λ(γ) ∈ R, γ ∈ (0, diam(D) 2 ), satisfy for every 2 2

β δ d γ ∈ (0, diam(D) 2 ) that λ(γ) = log(1 + γ d ). First, observe that the fact that for all x ∈ D, y ∈ Dδ it holds that r̄(x) ≤ r(x) and r̄(y) ≥ βr(y) ≥ βδ and Lemma 3.6 assure for every d γ ∈ (0, diam(D) 2 ), x ∈ Dδ that

  E eγTdiam(D) ≤

d d − γ diam(D)2

(41)

and

  β 2δ2 γr̄(x)2 ≥1+γ = eλ(γ) . (42) E eγTr̄(x) ≥ 1 + d d Throughout the remainder of this proof let Kδ : DN0 → N0 ∪ {+∞} satisfy for every x = (x0 , x1 , . . .) ∈ DN0 that Kδ (x) = inf{n ∈ N0 : r(xn ) < δ}. Observe that Kδ is measurable. Moreover, note that for all x ∈ D, j ∈ N it holds that Kδ (X̄ x,j ) = k̄δx,j . This, Lemma 3.5, the fact that P(kδx < ∞) = 1, (42), the fact that for all x ∈ D it holds that Tdiam(D) ≥ τkxδx , the monotone convergence theorem, and the law of total expectation yield d for all γ ∈ (0, diam(D) 2 ), x ∈ Dδ that  x,1  h γτ x i γ τ̄ x,1 kx ≥ E e δ = E e k̄δ h  P x,1
i k̄δ x,1 2 1 = E exp γ i=1 r̄ X̄i−1 ρi h  P x,1
i k̄δ ∧n x,1 2 1 = lim E exp γ i=1 r̄ X̄i−1 ρi n→∞ h h  P x,1 ii
 k̄δ ∧n x,1 2 1 = lim E E exp γ i=1 r̄ X̄i−1 ρi X̄ x,1 .

d ≥ E eγTdiam(D) d−γ diam(D)2





n→∞

11

(43)

The fact that Kδ (X̄ x,1 ) is σ(X̄ x,1 )-measurable and the fact that X̄ x,1 and (ρ1n )n∈N are d x,1 independent ensures for every x ∈ Dδ , n ∈ N, γ ∈ (0, diam(D) ), where 2 ) that ϕn,γ (X̄ h  P i Kδ (y)∧n 2 1 ϕn,γ (y) = E exp γ i=1 r̄(yi−1 ) ρi Z  P  Kδ (y)∧n 2 1 = exp γ i=1 r̄(yi−1 ) ρi (ω) P(dω),

(44) y ∈ DN0 ,

Ω

Pk̄δx,1 ∧n x,1 2 1 is (a version of) the conditional expectation E[exp(γ i=1 r̄(X̄i−1 ) ρi ) | X̄ x,1 ]. The fact that for all y ∈ DN0 , j ∈ {0, 1, . . . , Kδ (y)} it holds that yj−1 ∈ Dδ , (42), (44), and the d assumption that (ρ1n )n∈N are independent imply for all y ∈ DN0 , n ∈ N, γ ∈ (0, diam(D) 2) that (y)∧n h (y)∧n i KδY h i KδY γTr̄(yi−1 ) γ r̄(yi−1 )2 ρ1i = E e E e ≥ eλ(γ) = eλ(γ)(Kδ (y)∧n) .

Kδ (y)∧n

ϕn,γ (y) =

Y

i=1

i=1

(45)

i=1

d This, (43), and the monotone convergence theorem ensure for all x ∈ Dδ , γ ∈ (0, diam(D) 2) that ii h h  P x,1  
 k̄δ ∧n x,1 2 1 x,1 x,1 d X̄ X̄ = lim E ϕ ( X̄ ) r̄ ρ ≥ lim E E exp γ n,γ 2 i i−1 i=1 d−γ diam(D) n→∞ n→∞ h i h i x,1 λ(γ)(Kδ (X̄ )∧n) λ(γ)Kδ (X̄ x,1 ) ≥ lim E e =E e (46) n→∞   x,1  h i  x,1 2 2 k̄δ = E eλ(γ)k̄δ = E 1 + γ β dδ . d Choosing γ = 2 diam(D) 2 demonstrates for all x ∈ Dδ that

 k̄δx,1  β 2 δ2 E 1 + 2 diam(D)2 ≤ 2. This and Markov’s inequality yield for all x ∈ Dδ , M ∈ N that −M  x,1 β 2 δ2 P(k̄δ ≥ M ) ≤ 2 1 + 2 diam(D)2 .

(47)

(48)

This proves (40). This completes the proof of Lemma 3.7. The next lemma provides a probability measure to calculate expectations of integrals of time dependent functions of Brownian motion based on the time-space occupation behavior of Brownian motion. Lemma 3.8. Let U = {x ∈ Rd : ∥x∥ ≤h 1}, and let µ : iB([0, ∞) × U ) → [0, ∞) satisfy for Rζ all A ∈ B([0, ∞) × U ) that µ(A) = dE 0 1A (s, Bs ) ds . Then (i) it holds that µ is a probability measure and (ii) it holds for all measurable f : [0, ∞) × U → [−∞, ∞] where f is µ-integrable or satisfies f ≥ 0 that Z ζ  Z f (p)µ(dp) = dE f (s, Bs ) ds . (49) [0,∞)×U

0

12

hR i ζ Proof. Throughout this proof let ν : B([0, ∞) × U ) ∋ A 7→ E 0 1A (s, Bs ) ds ∈ [0, ∞]. First, observe that [28, e.g., Proposition 2.2.21 or 3.1.8] ensures that E[ζ] = d1 . This proves that ν is a finite measure with ν([0, ∞) × U ) = E[ζ] = d1 . This and the fact that for all A ∈ B([0, ∞) × U ) it holds that µ(A) = ν(A) = dν(A) prove item (i). Next, observe that E[ζ] through approximation by simple functions it holds for all measurable f : [0, ∞) × U → [−∞, ∞] where f is µ-integrable or satisfies f ≥ 0 that Z ζ  Z Z f (p)µ(dp) = d f (p)ν(dp) = dE f (s, Bs ) ds . (50) [0,∞)×U

[0,∞)×U

0

This proves item (ii). The proof of Lemma 3.8 is thus complete. In the following lemma, a representation of functions of the form (1) via the Walkon-Spheres process is provided. In the sense of Remark 2.5, this establishes a Walkon-Spheres based representation of solutions of the PDE (2) (see, e.g., [11, Lemma 3.4] and [6, Corollary 2.10] for similar results). Lemma 3.9. Assume δ = 0, let h0 : [0, ∞) × ∂D → R, h1 : [0, ∞) × D → R be measurable and bounded, let w : D → R satisfy for all x ∈ D that  Z τ x x h1 (s, x + Bs ) ds , (51) w(x) = E[h0 (τ , x + Bτ x )] + E 0

let µ be as in Lemma 3.8, let (Vk , Yk ) ∼ µ, k ∈ N, be independent, assume that ((Vk , Yk ))k∈N and B are independent. Then it holds for all x ∈ D that  w(x) = E h0 (τ x , x + Bτ x )   ∞ 1P 2 x 2 x x x x r̄(x + Bτk−1 ) h1 τk−1 + r̄(x + Bτk−1 ) Vk , x + Bτk−1 + r̄(x + Bτk−1 )Yk . (52) + d k=1 Proof. Throughout this proof let Tc : Ω → [0, ∞], c ∈ (0, ∞), satisfy for every c ∈ (0, ∞) that Tc = inf{t ∈ [0, ∞) : ∥Bt ∥ = c}. First, note that the assumption that δ = 0, [6, Remark 2.9], the assumption that h1 is bounded, and the dominated convergence ensure for all x ∈ D that "Z x # Z τ x  n τk X E h1 (s, x + Bs ) ds = lim E h1 (s, x + Bs ) ds . (53) 0

n→∞

k=1

x τk−1

The strong Markov property (cf., [19, Section 2.6]) and the scaling property imply for all

13

x ∈ D, k ∈ N that "Z x # τk E h1 (s, x + Bs ) ds x τk−1

 Z τ x −τ x k k−1 x x +s ) ds =E h1 (τk−1 + s, x + Bτk−1 0  Z τ x −τ x  k k−1 x x +s ) ds | Fτ x =E E h1 (τk−1 + s, x + Bτk−1 k−1 0  Z Tr̄(x+y )  0 = E E h1 (t0 + s, x + y0 + Bs ) ds

 

x ,B x (t0 ,y0 )=(τk−1 τ

0

k−1

)





  Z T1 2 2 h1 (t0 + r̄(x + y0 ) s, x + y0 + r̄(x + y0 )Bs ) ds = E E r̄(x + y0 )

. x ,B x (t0 ,y0 )=(τk−1 τ

0

k−1

)

(54) Throughout the remainder of this proof let U = {x ∈ Rd : ∥x∥ ≤ 1}. Furthermore, note that Lemma 3.8 and the assumption that (V1 , Y1 ) ∼ µ demonstrate for all measurable φ : [0, ∞) × U → [−∞, ∞] where φ is µ-integrable or satisfies φ ≥ 0 that that  Z T1 Z 1 1 φ(v, y)µ(d(v, y)) = E[φ(V, Y )]. (55) φ(s, Bs ) ds = E d [0,∞)×U d 0 This, the assumption that (Vk , Yk ) ∼ µ, k ∈ N, are independent, the assumption that ((Vk , Yk ))k∈N and B are independent, (53), and (54) establish for all x ∈ D that  Z τ x h1 (s, x + Bs ) ds E 0 "∞ #   (56) 1 X 2 x 2 x x x x = E r̄(x + Bτk−1 ) h1 τk−1 + r̄(x + Bτk−1 ) Vk , x + Bτk−1 + r̄(x + Bτk−1 )Yk . d k=1 This proves (52). The proof of Lemma 3.9 is thus complete.

4

Error analysis for the modified Walk-on-Spheres algorithm

In this section, we establish an error analysis for the estimator (5) as an approximation of expectations of type (1) in the L∞ -sense. To this end, we establish in Section 4.1 bias estimates for the Monte Carlo estimator (5). In Section 4.2 we first present some preparatory regularity properties of the Walk-on-Spheres process as well as the Monte Carlo estimator (5) and conclude with an overall error estimation in the L∞ -sense. The main results are Theorem 4.9 and Corollary 4.10. Throughout this section assume D ⊆ Rd to be open, bounded, and convex, let r : Rd → [0, ∞) satisfy for all x ∈ Rd that r(x) = inf{∥x − y∥ : y ∈ ∂D}, let β ∈ (0, 1], δ ∈ (0, ∞), let r̄ : D → [0, ∞) be a (β, δ)-distance on D, let τkx , X̄kx,j , τ̄kx,j , ζ, Zlj , ξlj , ρjl , x ∈ D, j, l ∈ N, k ∈ N0 , be as in Section 3, let h, h0 , h1 : [0, ∞) × D → R be measurable and bounded, let µ : B([0, ∞) × {x ∈ Rd : ∥x∥ ≤ 1}) → [0, 1] be as in Lemma 3.8. For n ∈ N, S ⊆ Rn , and F : S → R we denote with ∥F ∥∞ the supremum norm of F on its domain S, i.e., ∥F ∥∞ = sups∈S |F (s)|. 14

4.1

Bias estimates

Lemma 4.1. Let n, M ∈ N, L1 , L2 ∈ (0, ∞), assume for all t, s ∈ [0, ∞), x, y ∈ D that |h(t, x) − h(s, y)| ≤ L1 |t − s| + L2 ∥x − y∥,

(57)

let w : D → R satisfy for all x ∈ D that w(x) = E[h(τ x , x + Bτ x )], and let w̄ = w̄r̄,n,M : D× Ω → R satisfy for all x ∈ D that n

1X x,i x,i h τ̄M , X̄M . w̄(x) = n i=1

(58)

Then it holds for all x ∈ D that |w(x) − E[w̄(x)]| ≤ L1 diam(D)δ + L2 d

1/2

1/2

diam(D) δ

1/2



β 2 δ2 + 4∥h∥∞ 1 + 2 diam(D) 2

Proof. First, observe that Lemma 3.4 shows for all x ∈ D that n  x,i x,i  P , X̄M ) |w(x) − E[w̄(x)]| = E[h(τ x , x + Bτ x )] − n1 E h(τM i=1   x x ) = E h(τ x , x + Bτ x ) − h(τM , x + BτM 
 x x ) 1{M ≥k x } ≤ E h(τ x , x + Bτ x ) − h(τM , x + BτM δ 
 x x ) 1{M <k x } + E h(τ x , x + Bτ x ) − h(τM , x + BτM . δ

−M . (59)

(60)

Next, note that combining the triangle inequality, the fact that {M < kδx } ⊆ {M ≤ kδx }, and the assumption that h is bounded with Lemma 3.7 yields for all x ∈ D that 
 x x ) 1{M <k x } E h(τ x , x + Bτ x ) − h(τM , x + BτM δ −M  (61) β 2 δ2 x . ≤ 2∥h∥∞ E[1{M <kδ } ] ≤ 4∥h∥∞ 1 + 2 diam(D)2 Additionally, note that the assumption that for all t, s ∈ [0, ∞), x, y ∈ D it holds that x , Jensen’s inequality, the |h(t, x) − h(s, y)| ≤ L1 |t − s| + L2 ∥x − y∥, the fact that τ x ≥ τM x x x strong Markov property, the fact that {M ≥ kδ } ⊆ {τM ≥ τkδx } and Lemma 3.2, imply for all x ∈ D that 
 x x ) 1{M ≥k x } E h(τ x , x + Bτ x ) − h(τM , x + BτM δ     x x ∥1{M ≥k x } ≤ L1 E |τ x − τM |1{M ≥kδx } + L2 E ∥Bτ x − BτM δ i h  x  x x ∥1{τ x ≥τ x } ≤ L1 E |τ − τM |1{M ≥kδx } + L2 E ∥Bτ x − BτM M kx δ h h ii  x  x x ∥1{τ x ≥τ x } | Fτ x = L1 E |τ − τM |1{M ≥kδx } + L2 E E ∥Bτ x − BτM M M kx δ h  i  x   x x x x x x x = L1 E |τ − τM |1{M ≥kδ } + L2 E E ∥Bτ − BτM ∥ | FτM 1{τM ≥τkx } δ (62)  h  i1/2  x   1 x x x 1{τ x ≥τ x } ≤ L1 E |τ − τM |1{M ≥kδx } + L2 d /2 E E |τ x − τM | | FτM M kx δ   1 / 2  x    1 ≤ L1 E |τ − τkxδx | + L2 d /2 E |τ x − τkxδx |  h   h i i1/2 x+Bτ xx x+Bτ xx 1/2 k k δ | F x δ | F x ≤ L1 E E τ + L2 d E E τ τk x τk x δ

≤ L1 diam(D)δ + L2 d

1/2

δ

1/2

1/2

diam(D) δ .

Combining this with (61) proves (59). 15

Lemma 4.2. Let n, M ∈ N, let w : D → R satisfy for all x ∈ D that Z τ x  w(x) = E h(s, x + Bs ) ds ,

(63)

0

let (Vki , Yki ) ∼ µ, i, k ∈ N, be i.i.d., assume (Vki , Yki ), ρik , Zki , i, k ∈ N, and B are independent, and let w̄ = w̄r̄,n,M : D × Ω → R satisfy for all x ∈ D that n M
1X1X x,i x,i x,i 2 i x,i x,i 2 )Yki . + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 ) h τ̄k−1 r̄(X̄k−1 w̄(x) = n i=1 d k=1

(64)

Then it holds for all x ∈ D that  |w(x) − E[w̄(x)]| ≤ ∥h∥∞ diam(D)

2 diam(D) d



β 2 δ2 1 + 2 diam(D) 2

−M

 +δ .

(65)

Proof. First, observe that Lemmas 3.4 and 3.8, the techniques presented in the proof of Lemma 3.9, and the assumption that (Vk1 , Yk1 ), k ∈ N, are i.i.d. and independent from B establish that for all x ∈ D it holds that "Z x #  Z τ x τ M h(s, x + Bs ) ds w(x) = E h(s, x + Bs ) ds + E τx

0

"Z Mx τ =E

# h(s, x + Bs ) ds

x τM

M  i 1X h x x x x x + E r̄(x + Bτk−1 )2 h τk−1 + r̄(x + Bτk−1 )2 Vk1 , x + Bτk−1 + r̄(x + Bτk−1 )Yk1 d "Zk=1x # τ =E h(s, x + Bs ) ds x τM

M
 1X  x,1 2 x,1 x,1 2 1 x,1 x,1 E r̄(X̄k−1 ) h τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1 . + d k=1

(66) Next, note that Lemma 3.4 and the assumption that (Vki , Yki ), i, k ∈ N, are i.i.d. and independent from ρik , Zki , i, k ∈ N, and B imply for all x ∈ D that n M
 1 XX  x,i 2 x,i x,i 2 i x,i x,i E r̄(X̄k−1 ) h τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yki E[w̄(x)] = nd i=1 k=1 M
 1X  x,1 x,1 2 x,1 x,1 2 1 x,1 = E r̄(X̄k−1 ) h τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1 . d k=1

(67)

Combining (66), (67), and the triangle inequality with the assumption that h is bounded yields for all x ∈ D that "Z x # τ

|w(x) − E[w̄]| = E

h(s, x + Bs ) ds x τM

16

x ]. ≤ ∥h∥∞ E[τ x − τM

(68)

Next, observe that the strong Markov property, [6, Corollary 2.3], and Lemma 3.7 demonstrate for all x ∈ D that h h i i  x  x+Bτ x x M x x x E (τ − τM )1{M <kδ } = E E τ | FτM 1{M <kδ } (69)  −M 2 diam(D)2 diam(D)2 β 2 δ2 x P[kδ ≥ M ] ≤ 1 + 2 diam(D)2 . ≤ d d x Moreover, note that the strong Markov property, the fact that τ x ≥ τM , and Lemma 3.2 imply for all x ∈ D that  h h i i x+Bτ xx  x  x x x k δ | F x E (τ − τM )1{M ≥kδx } ≤ E τ − τkδx = E E τ τk x δ (70) h   i ≤ E r x + Bτkxx diam(D) ≤ δ diam(D). δ

Combining this and (69) with (68) proves (65). The proof of Lemma 4.2 is thus complete.

4.2

Global L∞ -error analysis

Lemma 4.3. Let n, M ∈ N, let (Vki , Yki ) ∼ µ, i, k ∈ N, be i.i.d. assume (Vki , Yki ), ρik , Zki , i, k ∈ N, are independent, and let w̄ = w̄r̄,n,M : D × Ω → R satisfy for all x ∈ D that   n M
1P 1P x,i x,i x,i 2 x,i x,i 2 i x,i x,i i w̄(x) = h0 (τ̄M , X̄M ) + r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk . n i=1 d k=1 (71) Then it holds for all x ∈ D, t ≥ 0 that P[|w̄(x) − E[w̄(x)]| ≥ t] ≤ 2 exp −

!

nt2 2

∥h1 ∥∞ 2 ∥h0 ∥∞ + M diam(D) d

2 .

(72)

Proof. Let w̄i = w̄i,δ,n,M : D × Ω → R, i ∈ N ∩ [1, n], satisfy for all i ∈ N ∩ [1, n], x ∈ D that M

x,i x,i w̄i (x) = h0 (τ̄M , X̄M )+

1X x,i 2 x,i x,i 2 i x,i x,i r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yki . (73) d k=1

Observe that for all x ∈ D it holds that (w̄i )i∈N∩[1,n] are independent and w̄(x) = Pn 1 w̄ i=1 i (x). Moreover, note that the assumption that for all x ∈ D it holds that n r̄(x) ≤ diam(D) and the assumption that hi , i ∈ {1, 2}, is bounded ensure for all i ∈ N ∩ [1, n], x ∈ D it holds that M diam(D)2 ∥h1 ∥∞ |w̄i (x)| ≤ ∥h0 ∥∞ + . d This and Hoeffding’s inequality show for all x ∈ D, t ≥ 0 that  n n   P P P[|w̄(x) − E[w̄(x)]| ≥ t] = P w̄i (x) − E w̄i (x) ≥ nt i=1

≤ 2 exp −

i=1

!

nt2 2

∥h1 ∥∞ 2 ∥h0 ∥∞ + M diam(D) d

This proves (72). The proof of Lemma 4.3 is thus complete. 17

(74)

2 .

(75)

Lemma 4.4. Let L ∈ [0, ∞) and assume for all x, y ∈ D that |r̄(x) − r̄(y)| ≤ L∥x − y∥. Then (i) it holds for all k ∈ N0 , i ∈ N, x, y ∈ D that ∥X̄kx,i − X̄ky,i ∥ ≤ (1 + L)k ∥x − y∥ and (ii) it holds for all k ∈ N0 , i ∈ N, x, y ∈ D that # " k P x,i y,i j−1 i |τ̄k − τ̄k | ≤ 2 diam(D)L (1 + L) ρj ∥x − y∥.

(76)

j=1

Proof. First, we prove item (i) via induction on k ∈ N0 . Note that for all i ∈ N, x, y ∈ D it holds that ∥X0x,i − X0y,i ∥ = ∥x − y∥. This proves item (i) for the base case k = 0. Let k ∈ N and assume item (i) holds true for all l ∈ N0 ∩ [0, k − 1]. This, the assumption that for all x, y ∈ D it holds that |r̄(x) − r̄(y)| ≤ L∥x − y∥, and the triangle inequality show for all i ∈ N, x, y ∈ D that x,i y,i x,i y,i ∥X̄kx,i − X̄ky,i ∥ ≤ ∥X̄k−1 − X̄k−1 ∥ + ∥ξki ∥|r̄(X̄k−1 ) − r̄(X̄k−1 )| x,i y,i ≤ (1 + L)∥X̄k−1 − X̄k−1 ∥ ≤ (1 + L)k ∥x − y∥.

(77)

This proves that item (i) holds true for all k ∈ N0 . Next, we prove item (ii) via induction on k ∈ N0 . Observe that for all i ∈ N, x, y ∈ D it holds that |τ̄0x,i − τ̄0y,i | = 0. This proves item (ii) for the base case k = 0. Let k ∈ N and assume item (ii) holds true for all l ∈ N0 ∩ [0, k − 1]. This, the assumption that for all x, y ∈ D it holds that |r̄(x) − r̄(y)| ≤ L∥x − y∥, the fact that for all x ∈ D it holds that r̄(x) ∈ [0, diam(D)], and item (i) demonstrate for all i ∈ N, x, y ∈ D that x,i y,i x,i 2 y,i 2 |τ̄kx,i − τ̄ky,i | ≤ |τ̄k−1 − τ̄k−1 | + |ρik ||r̄(X̄k−1 ) − r̄(X̄k−1 )| " # k−1 P x,i x,i ≤ 2 diam(D)L (1 + L)j−1 ρij ∥x − y∥ + 2 diam(D)Lρik ∥X̄k−1 − X̄k−1 ∥ j=1

" ≤ 2 diam(D)L (1 + L)k−1 ρik +

k−1 P

# (1 + L)j−1 ρij ∥x − y∥.

(78)

j=1

This proves that item (ii) holds true for all k ∈ N0 . The proof of Lemma 4.4 is thus complete. d+4 Lemma 4.5. Let (V, Y ) ∼ µ. Then it holds that E[V ] = 2d(d+2) .

Proof of Lemma 4.5. First, note that E[ζ] = d1 (cf. [28, e.g., Proposition 2.2.21 or 3.1.8]). Next, observe that Itô’s formula yields for all t ∈ [0, ∞) that Z t Z t 4 2 ∥Bt ∥ − 2(d + 2) ∥Bs ∥ ds = 4 ⟨Bs , dBs ⟩. (79) 0

0

R t∧ζ Let M = (Mt )t∈[0,∞) satisfy for all t ∈ [0, ∞) that Mt = 4 0 ⟨Bs , dBs ⟩. This and the fact that for all t ∈ [0, ζ] it holds that ∥Bs ∥ ≤ 1 implies that the local martingale M is indeed a square integrable martingale. Thus it holds for all t ∈ [0, ∞) that  Z t∧ζ 4 2 E[∥Bt∧ζ ∥ ] − 2(2 + d)E ∥Bs ∥ ds = 0. (80) 0

18

This, the dominated convergence theorem, and the monotone convergence theorem imply that Z  ζ

∥Bs ∥2 ds .

1 = 2(2 + d)E

(81)

0

Similarly, Itô’s product rule establishes for all t ∈ [0, ∞) that Z t Z t dt2 2 2 s⟨Bs , dBs ⟩. ∥Bs ∥ ds = 2 − t∥Bt ∥ − 2 0 0

(82)

Again this defines a local martingale, which stopped at ζ is a square integrable martingale. This, the dominated convergence theorem, and the monotone convergence theorem hence demonstrate that  Z ζ d 2 2 E[ζ] − E[ζ ] − E ∥Bs ∥ ds = 0. (83) 2 0 Combining this, the fact that E[ζ] = d1 , and (81) yields E[ζ 2 ] = d2d+4 . This and item (ii) (d+2) in Lemma 3.8 establish that  Z ζ Z d d+4 s ds = E[ζ 2 ] = vµ(d(v, y)) = dE . (84) E[V ] = 2 2d(d + 2) 0 [0,∞)×U The proof of Lemma 4.5 is thus complete. Lemma 4.6. Let n, M ∈ N, let (Vki , Yki ) ∼ µ, i, k ∈ N, be i.i.d., assume (Vki , Yki ), ρik , Zki , i, k ∈ N, are independent, let L, Lij ∈ [0, ∞), i ∈ {0, 1}, j ∈ {1, 2}, assume for all s, t ∈ [0, ∞), x, y ∈ D, i ∈ {0, 1} that |hi (s, x) − hi (t, y)| ≤ Li1 |s − t| + Li2 ∥x − y∥

and

|r̄(x) − r̄(y)| ≤ L∥x − y∥, (85)

let w̄ = w̄r̄,n,M : D × Ω → R satisfy for all x ∈ D that   n M
1P 1P x,i x,i x,i 2 x,i x,i 2 i x,i x,i i h0 (τ̄M , X̄M ) + r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk . w̄(x) = n i=1 d k=1 (86) Then (i) it holds for all x, y ∈ D that  2 diam(D)L01 |E[w̄(x)] − E[w̄(y)]| ≤ ∥x − y∥(1 + L) M L02 + d M

+ d1



2

2

2 diam(D)∥h1 ∥∞ + diam(D)



1

2 diam(D)L1 L12 + d

 (87)

(ii) it holds for all x, y ∈ D that  n M 2L0 diam(D) P P i 1 ∥∞ |w̄(x) − w̄(y)| ≤ ∥x − y∥(1 + L) L02 + 1 n ρj + 2M diam(D)∥h d M

i=1j=1

n M h k−1 P i i L12 M diam(D)2 2L1 diam(D)3 P P + 1 dn Vki + ρj + d j=1 i=1k=1

19

 .

(88)

Proof. First, note that Lemma 3.4, the assumption that (Vki , Yki ), i, k ∈ N are identically distributed, and the assumption that (Vki , Yki ), ρik , Zki , i, k ∈ N, are independent ensure for all x ∈ D that   x,1 x,1 E[w̄(x)] = E h0 (τ̄M , X̄M ) M (89)
  P x,1 x,1 x,1 2 x,1 x,1 2 1 + d1 E r̄(X̄k−1 + r̄(X̄k−1 )Yk1 . ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 k=1

This assures for all x, y ∈ D that h i x,1 x,1 y,1 y,1 |E[w̄(x)] − E[w̄(y)]| ≤ E h0 (τ̄M , X̄M ) − h0 (τ̄M , X̄M ) h M
P x,1 2 x,1 x,1 2 1 x,1 x,1 + d1 E r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1 k=1
i y,1 y,1 y,1 2 1 y,1 y,1 2 1 . − r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk (90) Next, observe that the assumption that for all i ∈ {0, 1}, s, t ∈ [0, ∞), x, y ∈ D it holds that |hi (s, x) − hi (t, y)| ≤ Li1 |s − t| + Li2 ∥x − y∥ and the fact that for all x ∈ D it holds that r̄(x) ≤ diam(D) imply for all k ∈ N ∩ [1, M ], x, y ∈ D that
x,1 2 x,1 x,1 2 1 x,1 x,1 r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1
y,1 2 y,1 y,1 2 1 y,1 y,1 − r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1 x,1 y,1 ≤ 2 diam(D)∥h1 ∥∞ |r̄(X̄k−1 ) − r̄(X̄k−1 )| 
x,1 y,1 x,1 2 y,1 2 + diam(D)2 L11 |τ̄k−1 − τ̄k−1 | + |Vk1 ||r̄(X̄k−1 ) − r̄(X̄k−1 )| 
x,1 y,1 x,1 y,1 1 1 + L2 ∥X̄k−1 − X̄k−1 ∥ + ∥Yk ∥|r̄(X̄k−1 ) − r̄(X̄k−1 )| .

(91)

This, the assumption that for all x, y ∈ D it holds that |r̄(x) − r̄(y)| ≤ L∥x − y∥, the fact that E[ζ] = d1 (cf. [28, e.g., Proposition 2.2.21 or 3.1.8]), the assumption that for all i, j ∈ N it holds that ρji and ζ are identically distributed, item (ii) in Lemma 3.8, k+4 Lemma 4.5, the fact that for all k ∈ N it holds that 2k(k+2) ≤ k1 , the fact that for all j, k ∈ N it holds that ∥Ykj ∥ ≤ 1, and Lemma 4.4 establish for all x, y ∈ D that h M
P x,1 2 x,1 2 1 x,1 x,1 x,1 1 1 E r̄( X̄ ) h + r̄( X̄ ) V , X̄ + r̄( X̄ )Y τ̄ 1 k k−1 k−1 k−1 k−1 k−1 k d k=1
i y,1 y,1 2 y,1 y,1 2 1 y,1 − r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk1  M h P k 1 ≤ ∥x − y∥ d (1 + L) 2 diam(D)∥h1 ∥∞

(92)

k=1

  i k−1 P + diam(D)2 L12 + 2L11 diam(D) E[Vk1 ] + E[ρ1j ] j=1    2 2L11 diam(D) MM 2 1 ≤ ∥x − y∥(1 + L) d 2 diam(D)∥h1 ∥∞ + diam(D) L2 + . d Similarly, it holds for all x, y ∈ D that h i   2M L01 diam(D) x,1 x,1 y,1 y,1 E h0 (τ̄M . , X̄M ) − h0 (τ̄M , X̄M ) ≤ ∥x − y∥(1 + L)M L02 + d 20

(93)

Combining this and (92) yields for all x, y ∈ D that  2L0 diam(D) M 2 |E[w̄(x)] − E[w̄(y)]| ≤ ∥x − y∥(1 + L) M L02 + 1 d    2L1 diam(D) + d1 2 diam(D)∥h1 ∥∞ + diam(D)2 L12 + 1 d

(94)

This proves item (i). Moreover, note that item (ii) is proven analogously. The proof of Lemma 4.6 is thus complete. Lemma 4.7. Let (V, Y ) ∼ µ. Then it holds for all t ∈ [0, ∞) that d

P[ζ ≥ t] ≤ 2e− 2 t

d

P[V ≥ t] ≤ 4e− 2 t .

and

(95) d

Proof of Lemma 4.7. First, observe that Lemma 3.6 yields that E[e 2 ζ ] ≤ 2. Combining this with Markov’s inequality demonstrates for all t ∈ [0, ∞) that d

d

d

P[ζ ≥ t] ≤ E[e 2 ζ ]e− 2 t ≤ 2e− 2 t .

(96)

Next, observe that item (ii) in Lemma 3.8 and Fubini’s theorem establish for all t ≥ 0 that  Z Z ∞

ζ

P[V ≥ t] = E[1[t,∞) (V )] = dE

P[ζ ≥ s] ds.

1[t,∞) (s) ds = d

(97)

t

0

This and (96) show for all t ∈ [0, ∞) that Z ∞ d d P[V ≥ t] ≤ 2d e− 2 s ds = 4e− s t .

(98)

t

The proof of Lemma 4.7 is thus complete. The next lemma is a modification of [6, Lemma 4.5]. We include a proof for the convenience of the reader. Lemma 4.8. Let X : Ω → [0, ∞) be a random variable, let c1 , c2 , c3 , c4 , A ≥ 0,
assume + 2 + c2 , c4 > 0, assume for all t ∈ [0, ∞) that P[X ≥ t] ≤ 2 ec1 −c2 ((t−A) ) + ec3 −c4 (t−A) . Then it holds that p c1 + log(2) + 1 c3 + log(2) + 1 E[X] ≤ A + + . (99) √ c2 c4 Proof of Lemma 4.8. Throughout this proof let λ ∈ R satisfy √ c1 +log(2) √ λ=A+ + c3 +log(2) . c2 c4

(100)

Observe that λ > A. This and the assumption that for all t ∈ [0, ∞) it holds that + 2 + P[X ≥ t] ≤ 2(ec1 −c2 ((t−A) ) + ec3 −c4 (t−A) ) ensures that Z ∞ Z ∞ E[X] = P[X ≥ t] dt ≤ λ + P[X ≥ t] dt 0 λ Z ∞ Z ∞ (101) c1 −c2 (t−A)2 c3 −c4 (t−A) ≤ λ + 2e e dt + 2e e dt. λ

λ

21

Next, note that the fact that it holds that λ − A ≥ c3 +log(2) implies that c4 Z ∞ 2 2 1 e−c4 (t−A) dt = ec3 −c4 (λ−A) ≤ e− log(2) = . 2ec3 (102) c4 c4 c4 λ √ p c1 +log(2) √ Moreover, observe that the fact that λ − A ≥ and the fact that 2 log(2) ≥ 1 c2 establish that Z ∞ Z ∞ Z ∞ 2ec1 2 −c2 s2 c1 −c2 (t−A)2 c1 e ds ≤ se−c2 s ds 2e e dt = 2e λ − A λ−A λ−A λ (103) ec1 e− log(2) 1 −c2 (λ−A)2 ≤ e ≤√ p ≤√ . (λ − A)c2 c2 c2 c1 + log(2) Combining this, (101), and (102) with (100) yields p c1 + log(2) + 1 c3 + log(2) + 1 1 1 E[X] ≤ λ + √ + =A+ + . √ c2 c4 c2 c4

(104)

The proof of Lemma 4.8 is thus complete. The following Theorem demonstrates that the estimator (5) approximates functions (1) in the L∞ -sense. The proof follows similar arguments as those presented in [6, Proof of Theorem 2.26]. Theorem 4.9. Let n, M ∈ N, let (Vki , Yki ) ∼ µ, i, k ∈ N, be i.i.d., assume (Vki , Yki ), ρik , Zki , i, k ∈ N, and B are independent, let L, Lij ∈ [0, ∞), i ∈ {0, 1}, j ∈ {1, 2}, assume for all s, t ∈ [0, ∞), x, y ∈ D, i ∈ {0, 1} that |hi (s, x) − hi (t, y)| ≤ Li1 |s − t| + Li2 ∥x − y∥

and

|r̄(x) − r̄(y)| ≤ L∥x − y∥, (105)

let w : D → R be continuous and satisfy for all x ∈ D that  Z τ x x h1 (s, x + Bs ) ds , w(x) = E[h0 (τ , x + Bτ x )] + E

(106)

0

let w̄ = w̄r̄,n,M : D × Ω → R satisfy for all x ∈ D that   n M
1P 1P x,i x,i x,i 2 x,i x,i 2 i x,i x,i i h0 (τ̄M , X̄M ) + r̄(X̄k−1 ) h1 τ̄k−1 + r̄(X̄k−1 ) Vk , X̄k−1 + r̄(X̄k−1 )Yk . w̄(x) = n i=1 d k=1 (107) Then it holds for all K ∈ N that   E sup|w(x) − w̄(x)| x∈D 1 1 1 ≤ (L01 + ∥h1 ∥∞ ) diam(D)δ + L02 d /2 diam(D) /2 δ /2  −M  2 ∥h ∥ β 2 δ2 1 ∞ 1 + + 4∥h0 ∥∞ + 2 diam(D) 2 d 2 diam(D)

    1/2 2L0 diam(D) 2L1 diam(D) d diam(D) + L02 + 1 d + d1 2 diam(D)∥h1 ∥∞ + diam(D)2 L12 + 1 d K   1/2 1 2 2M diam(D)∥h1 ∥∞ +L2 M diam(D) d diam(D) + L02 + d KM 2    √ √ M diam(D)2 ∥h1 ∥∞ 3 2

∥h0 ∥∞ +

+

d(log(K)+2 log(M )+M log(1+L))+log(2)+1 √ n

+

12 diam(D)2 (log(n)+log(M )+log(6)+1)(L01 d+L11 diam(D)2 M ) . d3/2 KM

d

(108) 22

Proof. We first note that the supremum supx∈D |w(x)− w̄(x)| is measurable because of the continuity of w and w̄. Throughout this proof, let K ∈ N be fixed and assume without loss of generality that D ⊆ [0, diam(D)]d . Let D ⊆ Rd satisfy that n od i diam(D) 2 M D = KM 2 (1+L)M : i ∈ N0 ∩ [0, KM (1 + L) ] ∩ D. (109) Note that for all x ∈ D there exist i1 , . . . , id ∈ N0 ∩ [0, KM 2 (1 + L)M ] such that  h  h id diam(D) (i1 +1) diam(D) (id +1) diam(D) i1 diam(D) × · · · × . , , x ∈ KM 2 (1+L)M KM 2 (1+L)M KM 2 (1+L)M KM 2 (1+L)M

(110)

This implies for all x ∈ D that there exists xD ∈ D such that ∥x − xD ∥ ≤ d1/2 KMdiam(D) 2 (1+L)M . This, Lemma 4.1, Lemma 4.2, and Lemma 4.6 demonstrate sup|w(x) − w̄(x)| x∈D

≤ sup|w(x) − E[w̄(x)]| + sup|w̄(x) − w̄(xD )| + sup|E[w̄(x)] − E[w̄(xD )]| x∈D

x∈D

x∈D

+ sup|w̄(y) − E[w̄(y)]| y∈D

≤ (L01 + ∥h1 ∥∞ ) diam(D)δ + L02 d /2 diam(D) /2 δ /2  −M  2 ∥h ∥ β 2 δ2 1 ∞ 1 + + 4∥h0 ∥∞ + 2 diam(D) d 2 diam(D)2     1/2 0 2L diam(D) 2L1 diam(D) d diam(D) + L02 + 1 d + d1 2 diam(D)∥h1 ∥∞ + diam(D)2 L12 + 1 d K   1 2M diam(D)∥h1 ∥∞ +L12 M diam(D)2 d /2 diam(D) + L02 + d KM 2 " #! n X M n X M k−1 X X X 1 0 1 3 2L1 diam(D) 2L diam(D) d /2 diam(D) + ρij + 1 dn Vki + ρij n KM 2 1

1

i=1 j=1

1

i=1 k=1

j=1

+ sup|w̄(y) − E[w̄(y)]| y∈D

= C(h0 , h1 , δ, d, D, K, M ) + Z, (111) where C(h0 , h1 , δ, d, D, K, M ) ∈ [0, ∞) and Z : Ω → [0, ∞) satisfy C(h0 , h1 , δ, d, D, K, M ) = (L01 + ∥h1 ∥∞ ) diam(D)δ + L02 d /2 diam(D) /2 δ /2  −M  2 ∥h ∥ β 2 δ2 1 ∞ 1 + + 4∥h0 ∥∞ + 2 diam(D) d 2 diam(D)2     1/2 0 2L1 diam(D) 2L11 diam(D) d diam(D) 1 0 2 1 + L2 + + d 2 diam(D)∥h1 ∥∞ + diam(D) L2 + d d K   1/2 1 M diam(D)2 2M diam(D)∥h ∥ +L d diam(D) 1 ∞ 2 + L02 + d KM 2 1

1

1

(112) and Z=

2L01 diam(D)

n X M X

n

ρij +

2L11 diam(D)3

" n X M X

dn

i=1 j=1

i=1 k=1

+ sup|w̄(y) − E[w̄(y)]|. y∈D

23

Vki +

k−1 X j=1

#! ρij

1

d /2 diam(D) KM 2

(113)

Moreover, note that the fact that for all i ∈ N it holds that ensures that Z≤

PM Pk−1 k=1

i j=1 ρk ≤ M

PM

i k=1 ρj

n M n M 2L11 diam(D)4 P P i 2 diam(D)2 (L01 d+L11 diam(D)2 M ) P P i ρ + Vk +sup|w̄(y) − E[w̄(y)]|. 1/2 1 k d nKM 2 d /2 nKM 2 y∈D i=1k=1 i=1k=1

(114)

Next, observe that the union bound inequality, Lemma 4.3, and (109) assure for all t ∈ [0, ∞) that !   X t 2 nt P sup|w̄(y) − E[w̄(y)]| ≥ ≤ 2 exp − M diam(D)2 ∥h1 ∥∞
2 3 y∈D 18 ∥h0 ∥∞ + y∈D d ! (115) ≤ 2 exp d(log(K) + 2 log(M ) + M log(1 + L)) −

nt2 M diam(D)2 ∥h1 ∥∞
2 18 ∥h0 ∥∞ + d

.

Moreover, note that Lemma 4.7 and the assumption that Vki , i, k ∈ N, are identically distributed demonstrate for all t ∈ [0, ∞) that   h i   n M 1/2 3 t 2L11 diam(D)4 P P i KM td /2 KM P d1/2 nKM 2 Vk ≥ ≤ 4nM exp − . ≤ nM P V11 ≥ 6Ltd 1 diam(D)4 12L11 diam(D)4 1 3 i=1k=1 (116) Furthermore, observe that Lemma 4.7 and the assumption that ρik , i, k ∈ N, are identically distributed imply for all t ∈ [0, ∞) that   i h n M 1 t 2 diam(D)2 (L01 d+L11 diam(D)2 M ) P P i 1 td /2 KM P ρ ≥ ≤ nM P ρ ≥ k 1 6 diam(D)2 (L01 d+L11 diam(D)2 M ) d1/2 nKM 2 3 i=1k=1   3 td /2 KM ≤ 2nM exp − 12 diam(D)2 (L0 d+L1 diam(D)2 M ) . 1

1

(117) Combining (114), (115), (116), and (117) with the union bound inequality establishes for all t ∈ [0, ∞) that P(Z ≥ t)  ≤ 2 exp d(log(K) + 2 log(M ) + M log(1 + L)) −

nt2 M diam(D)2 ∥h1 ∥∞
2 18 ∥h0 ∥∞ + d



    3/2 3 KM td /2 KM + 4nM exp − 12Ltd1 diam(D) + 2nM exp − 4 12 diam(D)2 (L01 d+L11 diam(D)2 M ) 1    nt2 ≤ 2 exp d(log(K) + 2 log(M ) + M log(1 + L)) − M diam(D)2 ∥h1 ∥∞
2

(118)

18 ∥h0 ∥∞ +

  d 3/2 td KM + exp log(3) + log(n) + log(M ) − 12 diam(D)2 (L . 0 d+L1 diam(D)2 M ) 1

1

This, (111), and Lemma 4.8 (applied with X ↶ Z, A ↶ 0, c1 ↶ d(log(K) + 2 log(M ) + M log(1 + L)), c3 ↶ log(3) + log(n) + log(M ),

c2 ↶

n , M diam(D)2 ∥h1 ∥∞
2 18 ∥h0 ∥∞ + d

3/2

(119)

KM c4 ↶ 12 diam(D)2 (Ld 0 d+L 1 diam(D)2 M ) 1

1

in the notation of Lemma 4.8) prove (108). The proof of Theorem 4.9 is thus complete. 24

Corollary 4.10. Assume the situation of Theorem 4.9, let ε ∈ (0, 1), and assume o n ε2 δ = min 1, 9((L0 +∥h ∥ ) diam(D)+L0 d1/2 diam(D)1/2 )2 , 2   1 1∞    log(6(2∥h0 ∥∞ d+diam(D)∥h1 ∥∞ ))−log(d)+log(ε−1 )  (120)    M = max 1,  and , β 2 δ2   log 1+  2 diam(D)2  n = K 2 = max 1, ⌈9C(h0 , h1 , d, D, M )2 ε−2 ⌉2 , where C(h0 , h1 , d, D, M ) ∈ [0, ∞) satisfies C(h0 , h1 , d, D, M )     1 2L01 diam(D) 2L11 diam(D) 0 2 1 1 = L2 + + d 2 diam(D)∥h1 ∥∞ + diam(D) L2 + d /2 diam(D) d d   2M diam(D)∥h1 ∥∞ +L12 M diam(D)2 d1/2 diam(D) + L02 + d M2    p √ √ 2 ∥h ∥ 1 ∞ + 3 2 1 + d + d(2 log(M ) + M log(1 + L)) + log(2) ∥h0 ∥∞ + M diam(D) d +

12 diam(D)2 (L01 d+L11 diam(D)2 M )(log(6)+3+log(M )) . d3/2 M

(121) Then it holds that E[supx∈D |w(x) − w̄(x)|] ≤ ε and there exist c, q ∈ (0, ∞) such that max{n, M } ≤ cdq ε−q , where q is an absolute constant and c depends only on L, L01 , L02 , L11 , L12 , ∥h0 ∥∞ , ∥h1 ∥∞ , β −1 , diam(D), and d and this dependency is at most polynomial.

5

ANN approximations and complexity analysis

In this section, we establish ANN approximation results for the approximation of functions of the form (1). To this end, we consider fully-connected feed forward ANNs with ReLU activation function as approximating ANNs. We adopt the notions of e.g., Jentzen et al. [17] (see also, e.g., Grohs et al. [13, Section 2], Grohs et al. [14, Section 3], Ackermann et al. [1, Section 2], and the references therein). In particular, these references establish an ANN calculus on the set of the considered ANNs encompassing operations such as composition, parallelization, and linear combination of (compatible) ANNs, as well es how the size of the ANNs behave under these operations. For simplicity, we consider in this section ANN approximations of functions w : D → R, w(x) = E[h(τ x , x + Bτ x )],

x ∈ D.

(122)

This corresponds to the special case of (1) with h0 = h and h1 ≡ 0. We refer to Remark 5.7 for a discussion on how to include non-zero h1 as well. In Section 5.1, we introduce the notion of ANNs that is employed in the remainder of this section. In Section 5.2, we provide ANN representation and approximation results for the Walk-on-Spheres process introduced in Section 3 and for the Monte Carlo estimator studied in Section 4. In Section 5.3, we combine the ANN representations and approximations from Section 5.2 with the error analysis established in Section 4 to obtain an ANN approximation of functions that satisfy (122) in the L∞ -sense.

25

5.1

ANN descriptions

Definition 5.1 (ANNs). We denote by N the set (of all ANNs) given by N=

S

L∈N

S

l0 ,l1 ,...,lL ∈N

× (R L k=1

lk ×lk−1

× Rlk ) .

(123)

Furthermore, for all L ∈ N, l0 , . . . , lL ∈ N, Φ = ((W1 , B1 ), . . . , (WL , BL )) ∈

× (R L k=1

lk ×lk−1

× Rlk ) ,

(124)

and x0 ∈ Rl0 , . . . , xL−1 ∈ RlL−1 with4 xk = M(Wk xk−1 + Bk ), k ∈ N0 ∩ [1, L − 1], we denote by L(Φ) = L W(Φ) = max

k∈N0 ∩[0,L]

P(Φ) =

l P

lk

lk (lk−1 + 1)

the length/depth of Φ, the maximum width of Φ, (125) the number of parameters of Φ,

k=1

and by R(Φ) ∈ C(Rl0 , RlL ) the function which satisfies (R(Φ))(x0 ) = WL xL−1 + BL .

5.2

ANN approximations of modified Walk-on-Spheres algorithms

The following lemma is a version of [35, Proposition 3], providing an ANN approximation of the product function R2 ∋ (x, y) → xy ∈ R on compact intervals. Lemma 5.2. There exist absolute constants κ1 , κ2 , κ3 ∈ [0, ∞) such that for all c ∈ (0, ∞), ε ∈ (0, 1] there exists Π ∈ N such that (i) it holds that R(Π) ∈ C(R2 , R), (ii) it holds for all x, y ∈ [−c, c] that |(R(Π))(x, y) − xy| ≤ ε, and
(iii) it holds that max{L(Π), W(Π)} ≤ κ1 + κ2 log2 1ε + κ3 (log2 (c))+ . The next two lemmas establish ANN representations and approximations of all processes appearing in the estimators of Section 4. More precisely, Lemma 5.3 establishes an ANN architecture that is used to represent the Walk-on-Spheres process and Lemma 5.4 provides an ANN architecture that is used to approximate the corresponding exit times. The proofs are consequences of induction as well as composition (see, e.g., [17, Proposition 2.1.2] [13, Proposition 2.6]), parallelization (see, e.g., [17, Lemma 2.2.14] [13, Corollary 2.23]), and summation (see, e.g., [13, Proposition 2.26]) of ANNs. Additionally, in the proof of Lemma 5.4 the ANN approximation of the product function Lemma 5.2 is used. A similar statement for the walk-on-spheres process itself (i.e., to Lemma 5.3) is formulated and proved in [6, Lemma 3.6, Corollary 3.7]. Lemma 5.3. Let d ∈ N, let r ∈ N satisfy that R(r) ∈ C(Rd , R) and min{L(r), W(r)} ≥ 2, let (pk )k∈N ⊆ Rd . Then there exist (Xk )k∈N0 ⊆ N such that For all d ∈ N, x = (x1 , . . . , xd ) ∈ Rd let M(x) ∈ Rd satisfy M(x) = (max{x1 , 0}, . . . , max{xd , 0}) (multidimensional version of ReLU activation function). 4

26

(i) it holds for all k ∈ N, x ∈ D that R(X0 ), R(Xk ) ∈ C(Rd , Rd ), (R(X0 ))(x) = x, and (R(Xk ))(x) = (R(Xk−1 ))(x) + (R(r))((R(Xk−1 ))(x))pk ,

(126)

and (ii) it holds for all k ∈ N that L(X0 ) = 1, W(X0 ) = d, L(Xk ) = k(L(r) − 1) + 1,

and

W(Xk ) ≤ 2d + W(r).

(127)

Lemma 5.4. Let d ∈ N, let D ⊆ Rd be open, bounded, let r ∈ N satisfy for all x ∈ D that R(r) ∈ C(Rd , R), min{L(r), W(r)} ≥ 2 and 0 ≤ (R(r))(x) ≤ r(x), let (pk )k∈N ⊆ Rd satisfy for all k ∈ N that ∥pk ∥ = 1, let (vk )k∈N ⊆ [0, ∞), and for every x ∈ D let (Pkx )k∈N0 ⊆ Rd , (Tkx )k∈N0 ⊆ [0, ∞) satisfy for every k ∈ N that P0x = x, Pkx = x x x x ))2 vk . Then there exist + ((R(r))(Pk−1 )pk , T0x = 0 and Tkx = Tk−1 + (R(r))(Pk−1 Pk−1 ε (Θk )(k,ε)∈N0 ×(0,1] ⊆ N (i) it holds for all k ∈ N, ε ∈ (0, 1], x ∈ D that R(Θε0 ), R(Θεk ) ∈ C(Rd , R), (R(Θε0 ))(x) = 0, |(R(Θεk ))(x) − Tkx | ≤ ε

k P

vj ,

(128)

j=1

and (ii) it holds for all k ∈ N, ε ∈ (0, 1] that L(Θε0 ) = 1, W(Θε0 ) = d,
L(Θεk ) ≤ κ1 + κ2 log2 1ε + κ3 log2 (diam(D)) + k(L(r) − 1), and (129) 
W(Θεk ) ≤ max{2, d} + k max κ1 + κ2 log2 1ε + κ3 log2 (diam(D)), 2d + W(r) , where κ1 , κ2 , κ3 ∈ [0, ∞) are the absolute constants from Lemma 5.2. The following lemma provides an ANN approximation of the Monte Carlo estimator (5) in the case of h1 ≡ 0. Before stating Lemma 5.5, we briefly explain some of the mathematical objects appearing in Lemma 5.5. The ANN r ∈ N in Lemma 5.5 denotes a function which determines the radii of the successive spheres on which the Walk-on-Spheres process takes place. For x ∈ D and index i ∈ {1, . . . , n} the sequence (Pkx,i )k∈N0 ⊆ Rd denotes the (deterministic) Walk-on-Spheres process, with start in x ∈ D, unit directions (pik )k∈N ⊆ Rd , and means of determining the radii of the successive spheres through the ANN r. The sequence (Tkx,i )k∈N0 ⊆ [0, ∞) denotes the corresponding exit times of successive spheres of the associated process (Pkx,i )k∈N0 , where the real number vki ∈ [0, ∞) takes on the role of the sampled exit time of a Brownian motion from the unit sphere. Lemma 5.5. Let d, n, M ∈ N, ε ∈ (0, 1], let D ⊆ Rd be open, bounded, let L ∈ [0, ∞), let h, r ∈ N satisfy for all x ∈ D, s, t ∈ R that R(h) ∈ C(Rd+1 , R), R(r) ∈ C(Rd , R), |(R(h))(s, x) − (R(h))(t, x)| ≤ L|s − t|, min{L(r), W(r)} ≥ 2, and 0 ≤ (R(r))(x) ≤ r(x), for every i ∈ N ∩ [1, n] let (pik )k∈N , ⊆ Rd satisfy for all k ∈ N that ∥pik ∥ = 1, for every i ∈ N ∩ [1, n] let (vki )k∈N ⊆ [0, ∞), and for every x ∈ D, i ∈ N ∩ [1, n] let (Pkx,i )k∈N0 ⊆ Rd , x,i x,i (Tkx,i )k∈N0 ⊆ [0, ∞) satisfy for every k ∈ N that P0x,i = x, Pkx,i = Pk−1 + (R(r))(Pk−1 )pik , x,i x,i x,i x,i r,ε T0 = 0 and Tk = Tk−1 + ((R(r))(Pk−1 ))2 vki . Then there exists Φ = Φn,M ∈ N such that 27

(i) it holds for all x ∈ D that (R(Φ))(x) −

n n P M 1P εL P x,i x,i (R(h))(TM , PM ) ≤ vi n i=1 n i=1k=1 k

(130)

and (ii) it holds that
L(Φ) ≤ L(h) + κ1 + κ2 log2 1ε + κ3 log2 (diam(D)) + M (L(r) − 1) and n W(Φ) ≤ n max W(h), max{2, d} + 2d + W(r) (131) o 
+ M max κ1 + κ2 log2 1ε + κ3 log2 (diam(D)), 2d + W(r) , where κ1 , κ2 , κ3 ∈ [0, ∞) are the absolute constants from Lemma 5.2. Proof. First, observe that Lemma 5.3 (applied for every i ∈ N ∩ [1, n] with d ↶ d, r ↶ r, (pk )k∈N ↶ (pik )k∈N in the notation of Lemma 5.3) and Lemma 5.4 (applied for every i ∈ N ∩ [1, n] with d ↶ d, D ↶ D, r ↶ r, (pk )k∈N ↶ (pik )k∈N , (vk )k∈N ↶ (vki )k∈N , (Pkx )(x,k)∈D×N0 ↶ (Pkx,i )(x,k)∈D×N0 , (Tkx )(x,k)∈D×N0 ↶ (Tkx,i )(x,k)∈D×N0 in the notation of Lemma 5.4) demonstrate that there exist (Xik )(i,k)∈(N∩[1,n]×N0 ) , (Θε,i k )(i,k)∈(N∩[1,n])×N0 ⊆ N such that (I) it holds for all i ∈ N ∩ [1, n], k ∈ N0 , x ∈ D that R(Xik ) ∈ C(Rd , Rd ), R(Θε,i k ) ∈ C(Rd , R), (R(Xik ))(x) = Pkx,i

and

x (R(Θε,i k ))(x) − Tk ≤ ε

k P

vj ,

(132)

j=1

and ε,1 (II) it holds for all i ∈ N ∩ [1, n], k ∈ N that D(Xik ) = D(X1k ), D(Θε,i k ) = D(Θk ), ε,i i L(Xi0 ) = L(Θε,i 0 ) = 1, W(X0 ) = W(Θ0 ) = d,

L(Xik ) = k(L(r) − 1) + 1, W(Xik ) ≤ 2d + W(r) (133)
ε,i 1 and L(Θk ) ≤ κ1 + κ2 log2 ε + κ3 log2 (diam(D)) + k(L(r) − 1), 
1 W(Θε,i k ) ≤ max{2, d} + k max κ1 + κ2 log2 ε + κ3 log2 (diam(D)), 2d + W(r) , where κ1 , κ2 , κ3 ∈ [0, ∞) are the absolute constants from Lemma 5.2. This [13, Proposition 2.6], [13, Corollary 2.23], and [1, Lemma 2.19] establish that there exists Φ ∈ N such that (A) it holds for all x ∈ D that R(Φ) ∈ C(Rd , R) and (R(Φ))(x) =

n
1P i (R(h)) (R(Θε,i M ))(x), (R(XM ))(x) n i=1

and

28

(134)

(B) it holds that
L(Φ) ≤ L(h) + κ1 + κ2 log2 1ε + κ3 log2 (diam(D)) + M (L(r) − 1) and n W(Φ) ≤ n max W(h), max{2, d} + 2d + W(r) (135) o 
+ M max κ1 + κ2 log2 1ε + κ3 log2 (diam(D)), 2d + W(r) . Observe that item (A), the assumption that for all x ∈ D, s, t ∈ R it holds that |(R(h))(s, x) − (R(h))(t, x)| ≤ L|s − t|, item (I), and the triangle inequality show for all x ∈ D that (R(Φ))(x) −

n n n P M LP εL P 1P x,i x,i x,i (R(h))(TM , PM ) ≤ (R(Θε,i vi . M )) − TM ≤ n i=1 n i=1 n i=1k=1 k

(136)

Combining this with item (B) proves items (i) and (ii). The proof of Lemma 5.5 is thus complete.

5.3

ANN approximations for solutions of elliptic PDEs

The next theorem is the main result of this section. We establish that under the assumptions stated below expectations of the form (122) can be approximated by ANNs in the L∞ -sense, where the size of the approximating ANNs is bounded by a polynomial expression depending on the problem inputs. In Remark 5.7, we discuss the implications of Theorem 5.6 for overcoming the curse of dimensionality in the approximation of expectations of the form (122) by ANNs. Moreover, we comment on further generalizations of Theorem 5.6. Theorem 5.6. Let d ∈ N, let D ⊆ Rd be open, bounded, and convex, let (Ω, F, P) be a probability space, let B : [0, ∞) × Ω → Rd be a standard Brownian motion, for every x ∈ D let τ x = inf{t ∈ [0, ∞) : x + Bt ∈ ∂D}, let L1 , L2 ∈ (0, ∞), let h ∈ N satisfy for all s, t ∈ [0, ∞), x, y ∈ D that R(h) ∈ C(Rd+1 , R), sup(u,z)∈[0,∞)×D |(R(h))(u, z)| < ∞, and |(R(h))(s, x) − (R(h))(t, y)| ≤ L1 |s − t| + L2 ∥x − y∥,

(137)

let w : D → R be continuous and satisfy for all x ∈ D that w(x) = E[(R(h))(τ x , x + Bτ x )], let η ∈ [0, ∞) be an absolute constant, let C ∈ [0, ∞), and let (rε )ε∈(0,1) ⊆ N satisfy for all x, y ∈ D, ε ∈ (0, 1) that R(rε ) ∈ C(Rd , R), P(rε ) ≤ Cε−η , |(R(rε ))(x) − r(x)| ≤ ε,

and

|(R(rε ))(x) − (R(rε ))(y)| ≤ C∥x − y∥.

(138)

Then there exist an absolute constant q ∈ [0, ∞) and a constant c ∈ [0, ∞) that depends only on diam(D), sup(u,z)∈[0,∞)×D |(R(h))(u, z)|, L1 , L2 , P(h), C, and d and this dependency is at most polynomial such that for every ε ∈ (0, 1) there exists Ψε ∈ N with sup|w(x) − (R(Ψε ))(x)| ≤ ε

and

P(Ψε ) ≤ cε−q .

(139)

x∈D

Proof. Throughout this proof let B = sup(u,z)∈[0,∞)×D |(R(h))(u, z)|, let Zkj : Ω → Rd , j, k ∈ N, be standard normally distributed, let ξkj : Ω → Rd , j, k ∈ N, satisfy for all j, k ∈ N that ξkj = ∥Zkj ∥−1 Zkj , let ζ : Ω → [0, ∞) satisfy ζ = inf{t ∈ [0, ∞)|∥Bt ∥ ≥ 1}, 29

let ρjk , k, j ∈ N, be i.i.d. copies of ζ, assume that ρjk , Zkj , j, k ∈ N are independent, let (δε )ε∈(0,1) ⊆ (0, 1] satisfy for all ε ∈ (0, 1) that   ε2 , (140) δε = min 1, 36(L1 diam(D) + L2 diam(D)1/2 d1/2 )2 let (Mε )ε∈(0,1) ⊆ N satisfy for all ε ∈ (0, 1) that     −1 log(24B) + log(ε )   ,  Mε = max 1,  δε2    log 1 + 

(141)

18 diam(D)2

let (γε )ε∈(0,1) ⊆ (0, 1] satisfy for all ε ∈ (0, 1) that n o γε = min 1, 2Ldε , 1 Mε

(142)

and let (nε )ε∈(0,1) ⊆ N satisfy for all ε ∈ (0, 1) that n  2 o nε = max 1, 36c(d, Mε , h, D, C)2 ε−2 ,

(143)

where   2L1 diam(D) 1/2 d1/2 diam(D) c(d, Mε , h, D, C) = L2 + d diam(D) + L2 d Mε2  p √  1/2 + 3 2B 1 + d + d(2 log(Mε ) + Mε log(1 + C)) + log(2) (144) +

12 diam(D)2 L1 (log(6) + 3 + log(Mε )) . d1/2 Mε

Combining [1, Lemma 3.2], [13, Proposition 2.6], and (138) with [6, Remark 2.8] demonstrates for all ε ∈ (0, 1) that there exists bε ∈ N such that it holds for all x ∈ Rd that R(bε ) ∈ C(Rd , R), L(bε ) = L(r δε ) + 1, W(bε ) ≤ W(r δε ), 3

3

(R(bε ))(x) = ((R(r δε ))(x) − ε)+ ,

(145)

3

and that R(bε ) is a ( 13 , δε )-distance (cf., Definition 3.3). Subsequently, for ε ∈ (0, 1) we denote by (X̄kx,j,ε )(x,k,j)∈D×N0 ×N the (family of) modified Walk-on-Spheres process and by (τ̄kx,j,ε )(x,k,j)∈D×N0 ×N the (family of) associated (physical) times generated by the ( 31 , δε )distance R(bε ) as well as the random variables ξki , ρik , i, k ∈ N (cf., Section 3). Moreover, for ε ∈ (0, 1) let w̄ε : D × Ω → R satisfy for all x ∈ D that n

ε 1 X x,i,ε x,i,ε w̄ε (x) = (R(h))(τ̄M , X̄M ). ε ε nε i=1

(146)

Next, observe that Lemma 5.5 (applied for every ω ∈ Ω, ε ∈ (0, 1) with d ↶ d, n ↶ nε , M ↶ Mε , ε ↶ γε , D ↶ D, L ↶ L1 , h ↶ h, r ↶ bε , (pik )(i,k)∈(N∩[1,n])×N ↶ (ξki (ω))(i,k)∈(N∩[1,n])×N , (vki )(i,k)∈(N∩[1,n])×N ↶ (ρik (ω))(i,k)∈(N∩[1,n])×N in the notation of Lemma 5.5) demonstrates that for every ε ∈ (0, 1) there exists Φε : Ω → N such that 30

(I) it holds for all ω ∈ Ω, x ∈ D that |(R(Φε (ω)))(x) − w̄ε (x, ω)| ≤

nε P Mε γε L1 P ρi (ω) nε i=1k=1 k

(147)

and (II) it holds for all ω ∈ Ω that   L(Φε (ω)) ≤ L(h) + κ1 + κ2 log2 γ1ε + κ3 log2 (diam(D)) + Mε (L(bε ) − 1) and n W(Φε (ω)) ≤ nε max W(h), max{2, d} + 2d + W(bε )   oo n + Mε max κ1 + κ2 log2 γ1ε + κ3 log2 (diam(D)), 2d + W(bε ) , (148) where κ1 , κ2 , κ3 ∈ [0, ∞) are the absolute constants from Lemma 5.2. This, (142), the assumption that (ρik ), i, k ∈ N, are identically distributed, and the fact that E[ρ11 ] = d1 (see [28, e.g., Proposition 2.2.21 or 3.1.8]) imply that for all ε ∈ (0, 1) it holds that   γε L1 Mε ε E sup|(R(Φε ))(x) − w̄ε (x)| ≤ = . (149) d 2 x∈D Next, note that Corollary 4.10 (applied for every ε ∈ (0, 1) with ε ↶ 2ε , h0 ↶ R(h), L01 ↶ L1 , L02 ↶ L2 , h1 ↶ 0, L11 ↶ 0, L12 ↶ 0, L ↶ L, r̄ ↶ R(bε ) in the notation of Corollary 4.10) yields for all ε ∈ (0, 1) that   ε E sup|w(x) − w̄ε (x)| ≤ . (150) 2 x∈D This, (149), and the triangle inequality yield for all ε ∈ (0, 1) that   E sup|w(x) − (R(Φε ))(x)| ≤ ε.

(151)

x∈D

This implies that there exists ωε ∈ Ω, ε ∈ (0, 1), such that for all ε ∈ (0, 1) it holds that sup|w(x) − (R(Φε (ωε )))(x)| ≤ ε.

(152)

x∈D

Next, observe that (140) and Jensen’s inequality ensure for all ε ∈ (0, 1) that  1 1 δε−1 = max 1, 36(L1 diam(D) + L2 diam(D) /2 d /2 )2 ε−2 ≤ (1 + 72 diam(D)(L21 diam(D) + L22 ))dε−2 .

(153)

This, (141), the fact that for all x ∈ (0, ∞) it holds that log(x) ≤ x, and the fact that for x all x ∈ (−1, ∞) it holds that log(1 + x) ≥ 1+x demonstrate for all ε ∈ (0, 1) that     −1 log(24B) + log(ε )    , Mε = max 1,  δε2    log 1 + 18 diam(D)  2 (154) −1 2 −2 −1 ≤ 2 + 18(log(24B) + log(ε )) diam(D) δε + log(24B) + log(ε ) ≤ c1 (h, D)d2 ε−5 , 31

where c1 (h, D) = 3 + log(24B) + 18(log(24B) + 1) diam(D)2 (1 + 72 diam(D)(L21 diam(D) + L22 ))2

(155)

This, the fact that for all x ∈ (0, ∞) it holds that log2 (x) ≤ x, and (142) imply for all ε ∈ (0, 1) that  1 Mε log2 (γε−1 ) ≤ γε−1 = max 1, 2Ldε ≤ (1 + 2L1 c1 (h, D))dε−6 . (156) Furthermore, observe that (144) and the fact that for all ε ∈ (0, 1) it holds that d, Mε ∈ N assure for all ε ∈ (0, 1) that c(d, Mε , h, D) ≤ c2 (h, D, C)Mε/2 d /2 ,

(157)

c2 (h, D, C) = 2 diam(D) L2 + 6 diam(D)L1 (1 + log(6)) p √
+ 3 2B 2 + 2 + log(2) + log(1 + C) .

(158)

1

1

where

This, (143), and Jensen’s inequality establish for all ε ∈ (0, 1) that nε ≤ 1 + (1 + 36c(d, Mε , h, D, C)2 ε−2 )2 ≤ 3 + 2592c2 (h, D, C)4 Mε2 d2 ε−4 .

(159)

This and (154) show for all ε ∈ (0, 1) that nε ≤ c3 (h, D, C)d6 ε−14 ,

(160)

where c3 (h, D, C) = 3+2592c1 (h, D)2 c2 (h, D, C)4 . Combining this, (152), [16, Lemma 3.3], the assumption that for all ε ∈ (0, 1) it holds that P(rε ) ≤ Cε−η , (153), (154), and (156) with item (II) proves (139). The proof of Theorem 5.6 is thus complete. Remark 5.7. We conclude this work with a few remarks concerning the conclusion of Theorem 5.6 as well as ways to extend the result. (i) Observe that Theorem 5.6 states an explicit polynomial dependence of the constant c in its conclusion on the problem dimension d. Moreover, additional implicit dependencies of c on d may arise through the remaining problem parameters appearing in the theorem such as for example diam(D). Theorem 5.6 implies that under the assumptions that these terms grow at most polynomially in the dimension d ∈ N, i.e., there exists an absolute constant K ∈ [0, ∞) such that for all T ∈ {diam(D), sup(u,z)∈[0,∞)×D |(R(h))(u, z)|, L1 , L2 , P(h), C} it holds that T ≤ KdK , the overall number of parameters of the approximating ANNs grows at most polynomially in the dimension d and the reciprocal ε−1 of the approximation accuracy ε. In this sense, the ANN approximation presented in Theorem 5.6 overcomes the curse of dimensionality. (ii) The assumption that h can be represented directly as an ANN can be weakened to the assumption that h can be approximated uniformly on [0, ∞) × D the size of these approximating ANNs appears in the dependency of the constant c in the conclusion of Theorem 5.6. (iii) Note that Lemmas 5.3 to 5.5 can be extended to include non-zero h1 under suitable assumptions as imposed on h0 (i.e., h) in the approximation of the Monte Carlo scheme (5). The statement and proof of Theorem 5.6 can be extended to this scenario as well. 32

References [1] Julia Ackermann, Arnulf Jentzen, Thomas Kruse, Benno Kuckuck, and Joshua Lee Padgett. Deep neural networks with ReLU, leaky ReLU, and softplus activation provably overcome the curse of dimensionality for Kolmogorov partial differential equations with Lipschitz nonlinearities in the lp -sense. arXiv:2309.13722, 2023. [2] Julia Ackermann, Arnulf Jentzen, Benno Kuckuck, and Joshua Lee Padgett. Deep neural networks with ReLU, leaky ReLU, and softplus activation provably overcome the curse of dimensionality for space-time solutions of semilinear partial differential equations. arXiv:2406.10876, 2024. [3] Christian Beck, Martin Hutzenthaler, Arnulf Jentzen, and Benno Kuckuck. An overview on deep learning-based approximation methods for partial differential equations. Discrete Contin. Dyn. Syst. Ser. B, 28(6):3697–3746, 2023. [4] Christian Beck, Arnulf Jentzen, Konrad Kleinberg, and Thomas Kruse. Nonlinear Monte Carlo methods with polynomial runtime for Bellman equations of discrete time high-dimensional stochastic optimal control problems. Appl. Math. Optim., 91(1):26, 2025. [5] Julius Berner, Philipp Grohs, and Arnulf Jentzen. Analysis of the generalization error: empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations. SIAM J. Math. Data Sci., 2(3):631–657, 2020. [6] Lucian Beznea, Iulian Cimpean, Oana Lupascu-Stamate, Ionel Popescu, and Arghir Zarnescu. From Monte Carlo to neural networks approximations of boundary value problems. arXiv:2209.01432, 2022. [7] Thomas E. Booth. Exact Monte Carlo solution of elliptic partial differential equations. J. Comput. Phys., 39(2):396–404, 1981. [8] Petru Cioica-Licht, Martin Hutzenthaler, and P Tobias Werner. Deep neural networks overcome the curse of dimensionality in the numerical approximation of semilinear partial differential equations. arXiv:2205.14398, 2022. [9] Avner Friedman. Stochastic differential equations and applications. Vol. 1. Probability and Mathematical Statistics, Vol. 28. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. [10] David Gilbarg and Neil S. Trudinger. Elliptic partial differential equations of second order. Classics in Mathematics. Springer-Verlag, Berlin, Heidelberg, 2001. [11] Philipp Grohs and Lukas Herrmann. Deep neural network approximation for high-dimensional elliptic PDEs with boundary conditions. IMA J. Numer. Anal., 42(3):2055–2082, 2022. [12] Philipp Grohs, Fabian Hornung, Arnulf Jentzen, and Philippe Von Wurstemberger. A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black–Scholes partial differential equations. Mem. Amer. Math. Soc., 284(1410), 2023. 33

[13] Philipp Grohs, Fabian Hornung, Arnulf Jentzen, and Philipp Zimmermann. Spacetime error estimates for deep neural network approximations for differential equations. Adv. Comput. Math., 49(1):4, 2023. [14] Philipp Grohs, Arnulf Jentzen, and Diyora Salimova. Deep neural network approximations for solutions of PDEs based on Monte Carlo algorithms. Partial Differ. Equ. Appl., 3(4):45, 2022. [15] Martin Hutzenthaler, Arnulf Jentzen, Thomas Kruse, and Tuan Anh Nguyen. A proof that rectified deep neural networks overcome the curse of dimensionality in the numerical approximation of semilinear heat equations. Partial Differ. Equ. Appl., 1:1–34, 2020. [16] Arnulf Jentzen, Konrad Kleinberg, and Thomas Kruse. Deep neural networks can provably solve Bellman equations for Markov decision processes without the curse of dimensionality. arXiv:2506.22851, 2025. [17] Arnulf Jentzen, Benno Kuckuck, and Philippe von Wurstemberger. Mathematical introduction to deep learning: Methods, implementations, and theory. arXiv:2310.20360, 2023. [18] Arnulf Jentzen, Diyora Salimova, and Timo Welti. A proof that deep artificial neural networks overcome the curse of dimensionality in the numerical approximation of Kolmogorov partial differential equations with constant diffusion and nonlinear drift coefficients. Commun. Math. Sci., 19(5):1167–1205, 2021. [19] Ioannis Karatzas and Steven E. Shreve. Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. [20] Achim Klenke. Probability theory. Universitext. Springer, London, second edition, 2014. [21] Andreas E. Kyprianou, Ana Osojnik, and Tony Shardlow. Unbiased ‘walk-on-spheres’ Monte Carlo methods for the fractional Laplacian. IMA J. Numer. Anal., 38(3):1550– 1578, 2018. [22] Pertti Mattila. Geometry of sets and measures in Euclidean spaces, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. Fractals and rectifiability. [23] Mervin E Muller. Some continuous Monte Carlo methods for the Dirichlet problem. The Annals of Mathematical Statistics, pages 569–589, 1956. [24] Thomas Müller-Gronbach, Erich Novak, and Klaus Ritter. Monte Carlo-Algorithmen. Springer-Verlag, 2012. [25] Ariel Neufeld and Tuan Anh Nguyen. Rectified deep neural networks overcome the curse of dimensionality in the numerical approximation of gradient-dependent semilinear heat equations. Commun. Math. Sci., 23(4):883–912, 2025.

34

[26] Ariel Neufeld and Tuan Anh Nguyen. Multilevel Picard approximations and deep neural networks with ReLU, leaky ReLU, and softplus activation overcome the curse of dimensionality when approximating semilinear parabolic partial differential equations in Lp -sense. J. Comput. Appl. Math., 487:Paper No. 117736, 32, 2026. [27] Ariel Neufeld, Tuan Anh Nguyen, and Sizhou Wu. Deep ReLU neural networks overcome the curse of dimensionality when approximating semilinear partial integrodifferential equations. Anal. Appl. (Singap.), 23(7):1127–1178, 2025. [28] Sidney C. Port and Charles J. Stone. Brownian motion and classical potential theory. Probability and Mathematical Statistics. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. [29] Christoph Reisinger and Yufei Zhang. Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems. Anal. Appl. (Singap.), 18(06):951–999, 2020. [30] Karl K. Sabelfeld. Random walk on spheres method for solving drift-diffusion problems. Monte Carlo Methods Appl., 22(4):265–275, 2016. [31] Karl K. Sabelfeld and Anastasya Kireeva. A new global random walk algorithm for calculation of the solution and its derivatives of elliptic equations with constant coefficients in an arbitrary set of points. Appl. Math. Lett., 107:106466, 9, 2020. [32] Karl K. Sabelfeld and Anastasya Kireeva. A global random walk on spheres algorithm for calculating the solution and its derivatives of the drift-diffusion-reaction equations. Math. Methods Appl. Sci., 45(3):1420–1431, 2022. [33] Karl K. Sabelfeld and Denis Talay. Integral formulation of the boundary value problems and the method of random walk on spheres. Monte Carlo Methods Appl., 1(1):1–34, 1995. [34] Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. Grid-free monte carlo for pdes with spatially varying coefficients. ACM Trans. Graph., 41(4), July 2022. [35] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103–114, 2017.

35

Related documents

• STVS-PINN: Segmented Training and Variable Scaling for Physics-Informed Neural Networks in Stiff PDEs#381306
• Neural network methods for PDEs and Perron-Frobenius operator problems: Neumann series, invariant densities, and test-space adaptivity#672803
• Beyond PINNs: A Unified Gauss--Newton and Petrov--Galerkin Framework for Neural and Hybrid PDE Solvers#1034445
• Beyond PINNs: A Unified Gauss--Newton and Petrov--Galerkin Framework for Neural and Hybrid PDE Solvers#978425
• Diff-NekRS: A Scalable Differentiable Framework for Multi-Timestep Solver-in-the-Loop Training#1048952