Christel Geiss

Céline Labart

Antti Luoto

MEAN SQUARE RATE OF CONVERGENCE FOR RANDOM WALK AP-PROXIMATION OF FORWARD-BACKWARD SDES

Keywords: Backward stochastic differential equations, approximation scheme, finite difference equation, convergence rate, random walk approximation 2010 Mathematics Subject Classification: Primary 60H10, 60H35, 60G50 Secondary 60H30

come

Mean square rate of convergence for random walk approximation of forward-backward SDEs

Introduction

Let (Ω, F , P) be a complete probability space carrying the standard Brownian motion B = (B t ) t≥0 and assume that (F t ) t≥0 is the augmented natural filtration. Let (Y, Z) be the solution of the forward-backward SDE (FBSDE)

X s = x + s 0 b(r, X r )dr + s 0 σ(r, X r )dB r , Y s = g(X T ) + T s f (r, X r , Y r , Z r )dr - T s Z r dB r , 0 ≤ s ≤ T. (1)
Let (Y n , Z n ) be the solution of the FBSDE if the Brownian motion B is replaced by a scaled random walk B n given by

B n t = √ h [t/h] i=1 ε i , 0 ≤ t ≤ T, (2)
where h = T n and (ε i ) i=1,2,... is a sequence of i.i.d. Rademacher random variables. Then (Y n , Z n ) solves the discretized FBSDE

X n s = x + (0,s] b(r, X n r-)d[B n ] r + (0,s] σ(r, X n r-)dB n r , Y n s = g(X n T ) + (s,T ] f (r, X n r-Y n r-, Z n r-)d[B n ] r - (s,T ] Z n r-dB n r , 0 ≤ s ≤ T. (3)
The approximation of BSDEs using random walk has been investigated by many authors, also numerically (see, for example, [START_REF] Briand | Donsker-Type theorem for BSDEs[END_REF], [START_REF] Jańczak-Borkowska | Discrete approximations of generalized RBSDE with random terminal time[END_REF], [START_REF] Ma | Numerical method for backward stochastic differential equations[END_REF], [START_REF] Martínez | Numerical Method for reflected backward stochastic differential equations[END_REF], [START_REF] Mémin | Convergence of solutions of discrete reflected backward SDE's and simulations[END_REF], [START_REF] Peng | Numerical algorithms for backward stochastic differential equations with 1-d Brownian motion: convergence and simulations[END_REF], [START_REF] Cheridito | BS∆Es and BSDEs with non-Lipschitz drivers: Comparison, convergence and robustness[END_REF]). In 2001, Briand et al. [START_REF] Briand | Donsker-Type theorem for BSDEs[END_REF] have shown weak convergence of (Y n , Z n ) to (Y, Z) for a Lipschitz continuous generator f and a terminal condition in L 2 . The rate of convergence of this method remained an open problem.

Bouchard and Touzi in [START_REF] Bouchard | Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations[END_REF] and Zhang in [START_REF] Zhang | A numerical scheme for BSDEs[END_REF] proposed instead of random walk an approach based on the dynamic programming equation, for which they established a rate of convergence. But this approach involves conditional expectations. Various methods to approximate these conditional expectations have been developed ( [START_REF] Gobet | A regression-based Monte Carlo method to solve backward stochastic differential equations[END_REF], [START_REF] Crisan | On the Monte-Carlo simulation of BSDEs: An improvement on the Malliavin weights[END_REF], [START_REF] Chassagneux | Cubature methods to solve BSDEs: Error expansion and complexity control[END_REF]). Also forward methods have been introduced

to approximate (1): a branching diffusion method ( [START_REF] Henry-Labordere | A numerical algorithm for a class of BSDEs via the branching process[END_REF]), a multilevel Picard approximation ( [START_REF] Weinan | On multilevel Picard numerical approximations for high-dimensional nonlinear parabolic partial differential equations and high-dimensional nonlinear backward stochastic differential equations[END_REF])

and Wiener chaos expansion ( [START_REF] Ph | Simulation of BSDEs by Wiener chaos expansion[END_REF]). Many extensions of (1) have been considered, among them schemes for reflected BSDEs ( [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF], [START_REF] Chassagneux | Rate of convergence for discrete-time approximation of reflected BSDEs arising in switching problems[END_REF]), high order schemes ( [START_REF] Chassagneux | Linear multistep schemes for BSDEs[END_REF], [START_REF] Chassagneux | Runge-Kutta schemes for backward stochastic differential equations[END_REF]), fully-coupled BSDEs ( [START_REF] Delarue | A forward-backward stochastic algorithm for quasi-linear PDEs[END_REF], [START_REF] Bender | Time discretization and Markovian iteration for coupled FBSDEs[END_REF]), quadratic BSDEs ( [START_REF] Chassagneux | Numerical Stability Analysis of the Euler Scheme for BSDEs[END_REF]), BSDEs with jumps ( [START_REF] Geiss | Simulation of BSDEs with jumps by Wiener chaos expansion[END_REF]) and McKean-Vlasov BSDEs ( [START_REF] Alanko | Regression-based Monte Carlo methods for solving nonlinear PDEs[END_REF], [START_REF] De Raynal | A cubature based algorithm to solve decoupled McKean-Vlasov forward-backward stochastic differential equations[END_REF], [START_REF] Chassagneux | Numerical Method for FBSDEs of McKean-Vlasov type[END_REF]).

The aim of this paper is to study the rate of the L 2 -approximation of (Y n t , Z n t ) to (Y t , Z t ) when X satisfies [START_REF] Alanko | Regression-based Monte Carlo methods for solving nonlinear PDEs[END_REF]. For this, we generate the random walk B n by Skorohod embedding from the Brownian motion B. In this case the L p -convergence of B n to B is of order h 1 4 for any p > 0.

The special case X = B has already been studied in [START_REF] Geiss | Random walk approximation of BSDEs with Hölder continuous terminal condition[END_REF], assuming a locally α-Hölder continuous terminal function g and a Lipschitz continuous generator. An estimate for the rate of convergence was obtained which is of order h α 4 for the L 2 -norm of Y n t -Y t , and of order h √ T -t for the L 2 -norm of Z n t -Z t . In the present paper, where we assume that X is a solution of the SDE in [START_REF] Alanko | Regression-based Monte Carlo methods for solving nonlinear PDEs[END_REF], rather strong conditions on the smoothness and boundedness on f and g and also on b and σ are needed. In Theorem 3.1, the main result of the paper, we show that the convergence rate for (Y n t , Z n t ) to (Y t , Z t ) in L 2 is of order h 1 4 ∧ α 2 provided that g ′′ is locally α-Hölder continuous. To the best of our knowledge, these are the first cases a convergence rate for the approximation of forward-backward SDEs using random walk has been obtained.

Remark 1.1. For the diffusion setting -in contrast to the case X = B -we can derive the convergence rate for (Y n t , Z n t ) to (Y t , Z t ) in L 2 only under strong smoothness conditions on the coefficients which include also that g ′′ is locally α-Hölder continuous (see Assumption 2.3 below).

These requirements appear to be necessary. This becomes visible in Subsection 2.2.2 where we introduce a discretized Malliavin weight to obtain a representation Ẑn for Z n . While it holds that Ẑn = Z n when X = B, in our case Ẑn does not coincide with Z n . However, one can show that the difference Ẑn t -Z n t converges to 0 in L 2 as n → ∞ using a Hölder continuity property (see (62) in Remark 4.1) for the space derivative of the generator in [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF]. For this Hölder continuity property to hold one needs enough smoothness in space from the solution u n to the finite difference equation associated to the discretized FBSDE [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF]. Provided that Assumption 2.3 holds we show the smoothness properties for u n in Proposition 4.2 applying methods known for Lévy driven BSDEs.

The paper is organized as follows: Section 2 contains the setting, main assumptions and the approximative representation Ẑn of Z n . Our main results about the approximation rate for the case of no generator (i.e. f = 0) and for the general case are in Section 3. One can see that in contrast to what is known for time discretization schemes, for random walk schemes the Lipschitz generator seems to cause more difficulties than the terminal condition: while in the case f = 0 we need that g ′ is locally α-Hölder continuous, in the case f = 0 is this property is required for g ′′ . In Section 4 we recall some needed facts about Malliavin weights, about the regularity of solutions to BSDEs and properties of the associated PDEs. Finally, we sketch how to prove growth and smoothness properties of solutions to the finite difference equation associated to the discretized FBSDE. Section 5 contains technical results which mainly arise from the fact that the construction of the random walk by Skorohod embedding forces us to compare our processes on different 'time lines', one coming from the stopping times of the Skorohod embedding, and the other one is ruled by the equidistant deterministic times due to the quadratic variation process [B n ].

Preliminaries

The SDE and its approximation scheme

We introduce

X t = x + t 0 b(s, X s )ds + t 0 σ(s, X s )dB s , 0 ≤ t ≤ T
and its discretized counterpart

X n t k = x + h k j=1 b(t j , X n tj-1 ) + √ h k j=1
σ(t j , X n tj-1 )ε j , t j := j T n , j = 0, ..., n,

where (ε i ) i=1,2,... is a sequence of i.i.d. Rademacher random variables. Letting

G k := σ(ε i : 1 ≤ i ≤ k) with G 0 := {∅, Ω}, it follows that the associated discrete-time random walk (B n t k ) n k=0 is (G k ) n k=0 -adapted. Recall (2) and h = T n .
If we extend the sequence (X n t k ) k≥0 to a process in continuous time by defining X n t := X n t k for t ∈ [t k , t k+1 ), it is the solution of the forward SDE (3). We formulate our first assumptions. Assumption 2.1 (ii) will be not used explicitely for our estimates but it is required for Theorem 4.1 below. Assumption 2.1.

(i) b, σ ∈ C 0,2 b ([0, T ] × R)
, in the sense that the derivatives of order k = 0, 1, 2 w.r.t. the space variable are continuous and bounded on [0, T ] × R, (ii) the first and second derivatives of b and σ w.r.t. the space variable are assumed to be γ-Hölder continuous (for some γ ∈ (0, 1], w.r.t. the parabolic metric d((t, x),

( t, x)) = (|t-t|+|x-x| 2 ) 1 2 )
on all compact subsets of [0, T ] × R.

(iii) b, σ are 1 2 -Hölder continuous in time, uniformly in space, (iv) σ(t, x) ≥ δ > 0 for all (t, x).

Assumption 2.2.

(i) g is locally Hölder continuous with order α ∈ (0, 1] and polynomially bounded (p 0 ≥ 0, C g > 0) in the following sense

∀(x, x) ∈ R 2 , |g(x) -g(x)| ≤ C g (1 + |x| p0 + |x| p0 )|x -x| α . ( 5
) (ii) The function [0, T ] × R 3 : (t, x, y, z) → f (t, x, y, z) satisfies |f (t, x, y, z) -f ( t, x, ȳ, z)| ≤ L f ( t -t + |x -x| + |y -ȳ| + |z -z|). (6)
Notice that (5) implies

|g(x)| ≤ K(1 + |x| p0+1 ) =: Ψ(x), x ∈ R, (7)
for some K > 0. From the continuity of f we conclude that

K f := sup 0≤t≤T |f (t, 0, 0, 0)| < ∞.
Notation:

• • p := • Lp(P)
for p ≥ 1 and for p = 2 simply • .

• If a is a function, C(a) represents a generic constant which depends on a and possibly also on its derivatives.

• E 0,x := E(•|X 0 = x). • Let φ be a C 0,1 ([0, T ] × R) function. φ x denotes ∂ x φ, the partial derivative of φ w.r.t. x.

The FBSDE and its approximation scheme

Recall the FBSDE (1) and its approximation [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF]. The backward equation in (3) can equivalently be written in the form

Y n t k = g(X n T ) + h n-1 m=k f (t m+1 , X n tm , Y n tm , Z n tm ) - √ h n-1 m=k Z n tm ε m+1 , 0 ≤ k ≤ n, (8)
if one puts X n r := X n tm , Y n r := Y n tm and Z n r := Z n tm for r ∈ [t m , t m+1 ).

Remark 2.1. Equations ( 3) and ( 8) do not contain any orthogonal part to the random walk B n since we are in a special case where the orthogonal part is zero. Indeed, for (

ε k ) k=1,••• ,n following the Rademacher law assume (G k := σ(ε i , i = 1, • • • , k))
as filtration, and let for the G n -measurable random variable F (ε 1 , ..., ε n ) hold the representation

F (ε 1 , ..., ε n ) = c + n m=1 h m ε m + N n ,
where (h m ) n m=1 is predictable and (N m ) n m=1 a martingale orthogonal to (B n tm ) n m=1 given by B n tm = √ h(ε 1 + ... + ε m ). By definition, orthogonality of the martingales N and B n means that their product is a martingale, i.e. we have

E[N k+1 B n t k+1 |G k ] = N k B n t k , and since N k B n t k = E[N k+1 B n t k |G k ], this implies especially that EN k+1 ε k+1 = 0. Assume N k+1 is given by N k+1 = H(ε 1 , ..., ε k+1 ). Then 0 = EH(ε 1 , ..., ε k+1 )ε k+1 = 1 2 [H(ε 1 , ..., ε k , 1)-H(ε 1 , ..., ε k , -1)] implying that N k+1 is G k -measurable since H(ε 1 , ..., ε k , 1) = H(ε 1 , ..., ε k , -1)
, and therefore the martingale (N m ) n m=1 is identically zero. (See also [5, page 3] or [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings-With Normal Martingales[END_REF]Proposition1.7.5].)

One can derive an equation for Z n = (Z n t k ) n-1 k=0 if one multiplies (8) by ε k+1 and takes the conditional expectation w.r.t. G k , so that

Z n t k = E G k (g(X n T )ε k+1 ) √ h + E G k √ h n-1 m=k+1 f (t m+1 , X n tm , Y n tm , Z n tm )ε k+1 , 0 ≤ k ≤ n -1, (9)
where

E G k := E(•|G k ).
Z t = E t g(X T )N t T + T t f (s, X s , Y s , Z s )N t s ds σ(t, X t ), 0 ≤ t ≤ T (10)
where E t := E(•|F t ), and for all s ∈ (t, T ], we have (cf. Lemma 4.1)

N t s = 1 s -t s t ∇X r σ(r, X r )∇X t dB r , (11)
where ∇X = (∇X s ) s∈[0,T ] is the variational process i.e. it solves

∇X s = 1 + s 0 b x (r, X r )∇X r dr + s 0 σ x (r, X r )∇X r dB r , (12)
with (X s ) s∈[0,T ] given in (1).

Remark 2.3. In the following we will assume that g ′′ exists. In such a case we have the following representation for Z:

Z t = E t g ′ (X T )∇X T + T t f (s, X s , Y s , Z s )N t s ds σ(t, X t ), 0 ≤ t ≤ T. (13)
2.2.2. Approximation for Z n In this section we state the discrete counterpart to [START_REF] Chassagneux | Linear multistep schemes for BSDEs[END_REF], which, in the general case of a forward process X, does not coincide with Z n (given by ( 9)). In contrast to the continuous-time case, where the variational process and the Malliavin derivative are connected by ∇Xt ∇Xs = DsXt σ(s,Xs) (s ≤ t), we can not expect equality for the corresponding expressions if we use the discretized version of the processes (∇X t ) t and (D s X t ) s≤t introduced in [START_REF] De Raynal | A cubature based algorithm to solve decoupled McKean-Vlasov forward-backward stochastic differential equations[END_REF]. This counterpart Ẑn to Z is a key tool in the proof of the convergence of Z n to Z. As we will see in the proof of Theorem 3.1, the study of Z n t k -Z t k goes through the study of

Z n t k -Ẑn t k and Ẑn t k -Z t k .
Before defining the discretized version of (∇X t ) t and (D s X t ) s≤t , we shortly introduce the discretized Malliavin derivative and refer the reader to [START_REF] Bender | Discretizing Malliavin calculus[END_REF] for more information on this topic.

T m,± F (ε 1 , . . . , ε n ) := F (ε 1 , . . . , ε m-1 , ±1, ε m+1 , . . . , ε n ), 1 ≤ m ≤ n.
For any ξ = F (ε 1 , . . . , ε n ), the discretized Malliavin derivative is defined by

D n m ξ := E[ξε m |σ((ε l ) l∈{1,...,n}\{m} )] √ h = T m,+ ξ -T m,-ξ 2 √ h , 1 ≤ m ≤ n. ( 14
) Definition 2.2. (Definition of φ (k,l) x .) Let φ be a C 0,1 ([0, T ] × R) function. We denote φ (k,l) x := D n k φ(t l , X n t l-1 ) D n k X n t l-1 := 1 0 φ x (t l , ϑT k,+ X n t l-1 + (1 -ϑ)T k,-X n t l-1 )dϑ.
If D n k X n t ℓ-1 = 0 the second ′ := ′ holds as an identity.

We are now able to define the discretized version of (∇X t ) t and (D s X t ) s≤t .

Definition 2.3. (Discretized processes (∇X n,t k ,x tm ) m∈{k,...,n} and (D n k X n tm ) m∈{k,...,n} .) For all m in {k, . . . , n} we define

∇X n,t k ,x tm = 1 + h m l=k+1 b x (t l , X n,t k ,x t l-1 )∇X n,t k ,x t l-1 + √ h m l=k+1 σ x (t l , X n,t k ,x t l-1 )∇X n,t k ,x t l-1 ε l , 0 ≤ k ≤ n, D n k X n tm = σ(t k , X n t k-1 ) + h m l=k+1 b (k,l) x D n k X n t l-1 + √ h m l=k+1 σ (k,l) x (D n k X n t l-1 )ε l , 0 < k ≤ n. ( 15
) Remark 2.4. (i) Although ∇X n,t k ,X n t k tm is not equal to D n k+1 X n tm σ(t k+1 ,X n t k
) , we can show that the difference of these terms converges in L p (see Lemma 5.4).

(ii) With the notation introduced above, (9) rewrites to

Z n t k = E G k D n k+1 g(X n T ) + E G k h n-1 m=k+1 D n k+1 f (t m+1 , X n tm , Y n tm , Z n tm ) . (16)
In order to define the discrete counterpart to [START_REF] Chassagneux | Linear multistep schemes for BSDEs[END_REF], we first define the discrete counterpart to ] given in [START_REF] Chassagneux | Numerical Method for FBSDEs of McKean-Vlasov type[END_REF]:

(N t s ) s∈[t,T
N n,t k t ℓ := √ h ℓ m=k+1 ∇X n,t k ,X n t k tm-1 σ(t m , X n tm-1 ) ε m t ℓ -t k , k < ℓ ≤ n. (17)
Notice that there is some constant κ 2 > 0 depending on b, σ, T, δ such that

E G k |N n,t k t ℓ | 2 1 2 ≤ κ 2 (t ℓ -t k ) 1 2 , 0 ≤ k < ℓ ≤ n. ( 18
)
Definition 2.4. (Discrete counterpart to [START_REF] Chassagneux | Rate of convergence for discrete-time approximation of reflected BSDEs arising in switching problems[END_REF].) Let the process Ẑn = ( Ẑn t k ) n-1 k=0 be defined by

Ẑn t k := E G k D n k+1 g(X n T ) + E G k h n-1 m=k+1 f (t m+1 , X n tm , Y n tm , Z n tm )N n,t k tm σ(t k+1 , X n t k ), (19)
Remark 2.5. In [START_REF] Karoui | Backward stochastic differential equations in finance[END_REF] We could have used also the approximate expression

E G k (g(X n T )N n,t k tn σ(t k+1 , X n t k )
), but since we will assume that g ′′ exists, we work with the correct term.

The study of the convergence E G 0,x |Z n t k -Ẑn t k | 2 requires stronger assumptions on the coefficients b, σ, f and g. Assumption 2.3. Assumptions 2.1 and 2.2 hold. Additionally, we assume that all first and second derivatives w.r.t. the variables x, y, z of b(t, x), σ(t, x) and f (t, x, y, z) exist and are bounded Lipschitz functions w.r.t. these variables, uniformly in time. Moreover, g ′′ satisfies (5).

E G 0,x |Z n t k -Ẑn t k | 2 ≤ C 2.1 Ψ2 (x)h α ,
where E G 0,x := E G (•|X 0 = x), the function Ψ is defined in (61) below, and C 2.1 depends on b, σ, f, g, T, p 0 and δ.

Proof. According to [START_REF] Briand | Donsker-Type theorem for BSDEs[END_REF]Proposition 5.1] one has the representations

Y n tm = u n (t m , X n tm ), and
Z n tm = D n m+1 u n (t m+1 , X n tm+1 ), ( 20
)
where u n is the solution of the finite difference equation [START_REF] Zhang | Some fine properties of backward stochastic differential equations, with applications[END_REF] with terminal condition u n (t n , x) = g(x). Notice that by the definition of D n m+1 in [START_REF] Chassagneux | Cubature methods to solve BSDEs: Error expansion and complexity control[END_REF] the expression D n m+1 u n (t m+1 , X n tm+1 ) depends in fact on X n tm . Hence we can put

f (t m+1 , X n tm , Y n tm , Z n tm ) = f (t m+1 , X n tm , u n (t m , X n tm ), D n m+1 u n (t m+1 , X n tm+1 )) =: F n (t m+1 , X n tm ).
From [START_REF] Karoui | Backward stochastic differential equations in finance[END_REF] and [START_REF] Cheridito | BS∆Es and BSDEs with non-Lipschitz drivers: Comparison, convergence and robustness[END_REF] we conclude that (we use E := E G 0,x for • )

Z n t k -Ẑn t k = E G k h n-1 m=k+1 D n k+1 f (t m+1 , X n tm , Y n tm , Z n tm ) -E G k h n-1 m=k+1 f (t m+1 , X n tm , Y n tm , Z n tm )N n,t k tm σ(t k+1 , X n t k ) ≤ n-1 m=k+1 h m -k m ℓ=k+1 E G k D n k+1 F n (t m+1 , X n tm ) -D n ℓ F n (t m+1 , X n tm ) σ(t k+1 , X n t k )∇X n,t k ,X n t k t ℓ-1 σ(t ℓ , X n t ℓ-1 )
.

With the notation introduced in Definition 2.2 applied to F n ,

D n k+1 F n (t m+1 , X n tm ) -D n ℓ F n (t m+1 , X n tm ) σ(t k+1 , X n t k )∇X n,t k ,X n t k t ℓ-1 σ(t ℓ , X n t ℓ-1 ) ≤ (D n k+1 X n tm )(F n,(k+1,m+1) x -F n,(ℓ,m+1) x ) + F n,(ℓ,m+1) x (D n k+1 X n tm ) -(D n ℓ X n tm ) σ(t k+1 , X n t k )∇X n,t k ,X n t k t ℓ-1 σ(t ℓ , X n t ℓ-1 ) =: A 1 + A 2 .
For A 1 we use Definition 2.2 again and exploit the fact that

x → F n x (t m+1 , x) := ∂ x f (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1 ))
is locally α-Hölder continuous according to (62). By Hlder's inequality and Lemma 5.4 (i) and

(iii),

A 1 ≤ D n k+1 X n tm 4 1 0 F n x (t m+1 , ϑT k+1,+ X n tm + (1 -ϑ)T k+1,-X n tm ) -F n x (t m+1 , ϑT ℓ,+ X n tm + (1 -ϑ)T ℓ,-X n tm ) 4 dϑ ≤ C(b, σ, f, g, T, p 0 ) Ψ(x)h α 2 .
For the estimate of A 2 we notice that by our assumptions the L 4 -norm of F n,(ℓ,m+1) x is bounded by CΨ 2 (x), so that it suffices to estimate

(D n k+1 X n tm ) -(D n ℓ X n tm ) σ(t k+1 , X n t k )∇X n,t k ,X n t k t ℓ-1 σ(t ℓ , X n t ℓ-1 ) 4 ≤ (D n k+1 X n tm ) - σ(t k+1 , X n t k ) D n ℓ X n tm σ(t ℓ , X n t ℓ-1 ) D n k+1 X n t ℓ-1 σ(t k+1 , X n t k ) 4 + σ(t k+1 , X n t k ) D n ℓ X n tm σ(t ℓ , X n t ℓ-1 ) ∇X n,t k ,X n t k t ℓ-1 - D n k+1 X n t ℓ-1 σ(t k+1 , X n t k ) 4 . (21)
The second expression on the r.h.s. of ( 21) is bounded by C(b, σ, T, δ)h 1 2 as a consequence of Lemma 5.4 (ii)-(iii). To show that also the first expression is bounded by C(b, σ, T, δ)h 1 2 , we rewrite it using [START_REF] De Raynal | A cubature based algorithm to solve decoupled McKean-Vlasov forward-backward stochastic differential equations[END_REF] and get

D n ℓ X n tm σ(t ℓ , X n t ℓ-1 ) D n k+1 X n t ℓ-1 -D n k+1 X n tm = 1 + m l=ℓ+1 D n ℓ X n t l-1 σ(t ℓ , X n t ℓ-1 ) (b (ℓ,l) x h + σ (ℓ,l) x √ hε l ) × σ(t k+1 , X n t k ) + ℓ-1 l=k+2 D n k+1 X n t l-1 (b (k+1,l) x h + σ (k+1,l) x √ hε l ) -σ(t k+1 , X n t k ) + ℓ-1 l=k+2 + m l=ℓ D n k+1 X n t l-1 (b (k+1,l) x h + σ (k+1,l) x √ hε l ) ≤ D n k+1 X n t ℓ-1 (b (k+1,ℓ) x h + σ (k+1,ℓ) x √ hε ℓ ) + m l=ℓ+1 D n ℓ X n t l-1 σ(t ℓ , X n t ℓ-1 ) D n k+1 X n t ℓ-1 -D n k+1 X n t l-1 b (ℓ,l) x h + σ (ℓ,l) x √ hε l + m l=ℓ+1 D n k+1 X n t l-1 b (ℓ,l) x h + σ (ℓ,l) x √ hε l -b (k+1,l) x h + σ (k+1,l) x √ hε l . ( 22
)
We take the L 4 -norm of ( 22) and apply the BDG inequality and Hölder's inequality. The second term on the r.h.s. of ( 22) will be used for Gronwall's lemma, while the first and the last one can be bounded by C(b, σ, T )h 1 2 , by using Lemma 5.4-(iii). For the last term we also use the Lipschitz continuity of b x and σ x in space and Lemma 5.4-(i).

Main results

In order to compute the mean square distance between the solution to (1) and the solution to

(3) we construct the random walk B n from the Brownian motion B by Skorohod embedding. Let

τ 0 := 0 and τ k := inf{t > τ k-1 : |B t -B τ k-1 | = √ h}, k ≥ 1. ( 23
) Then (B τ k -B τ k-1 ) ∞ k=1 is a sequence of i.i.d. random variables with P(B τ k -B τ k-1 = ± √ h) = 1 2 , which means that √ hε k d = B τ k -B τ k-1 . We will denote by E τ k the conditional expectation w.r.t. F τ k := G k .
In this case we also use the notation X τ k := X n t k for all k = 0, . . . , n, so that (4) turns into

X τ k = x + k j=1 b(t j , X τj-1 )h + k j=1 σ(t j , X τj-1 )(B τj -B τj-1 ), 0 ≤ k ≤ n.
Assumption 3.1. We assume that the random walk B n in (3) is given by

B n t = [t/h] k=1 (B τ k -B τ k-1 ), 0 ≤ t ≤ T,
where the τ k , k = 1, ..., n are taken from [START_REF] Gobet | A regression-based Monte Carlo method to solve backward stochastic differential equations[END_REF].

Remark 3.1. Note that for p > 0 there exists a C(p) > 0 such that for all k = 1, . . . , n it holds

1 C(p) (t k h) 1 4 ≤ (E|B τ k -B t k | p ) 1 p ≤ C(p)(t k h) 1 4 .
The upper estimate is given in Lemma 5.1. For p ∈ [4, ∞) the lower estimate follows from [2, Proposition 5.3]. We get the lower estimate for p ∈ (0, 4) by choosing 0 < θ < 1 and 0 < p < p 1

such that 1 4 = 1-θ p + θ p1 .
Then it holds by the log-convexity of L p norms (see, for example [START_REF] Tao | An Epsilon of Room I: Real Analysis[END_REF]Lemma 1.11.5]) that

B τ k -B t k 1-θ p ≥ B τ k -B t k 4 B τ k -B t k θ p1 ≥ C(4) -1 (t k h) 1 4 C(p 1 )(t k h) 1 4 θ ≥ C(p)(t k h) 1 4 1-θ . Since for t ∈ [t k , t k+1 ) it holds B n t = B τ k and B t -B t k p ≤ C(p)h 1 2
, we have for any p > 0 that

sup 0≤t≤T B n t -B t p = O(h 1 4 ). ( 24
) Proposition 3.1 states the convergence rate of (Y v , Z v ) to (Y n v , Z n v )
in L 2 when f = 0 and Theorem 3.1 generalizes this result for any f which satisfies Assumption 2.3. Proposition 3.1. Let Assumptions 2.1 and 3.1 hold. If f = 0 and g ∈ C 1 is such that g ′ is a locally α-Hölder continuous function in the sense of (5), then for all 0 ≤ v < T , we have (for

sufficiently large n) that E 0,x |Y v -Y n v | 2 ≤ C y 3.1 Ψ(x) 2 h 1 2 , and E 0,x |Z v -Z n v | 2 ≤ C z 3.1 Ψ(x) 2 h α 2 ,
where

C y 3.1 = C(C g , b, σ, T, p 0 , δ) and C z 3.1 = C(C g ′ , b, σ, T, p 0 , δ).
Theorem 3.1. Let Assumptions 2.3 and 3.1 be satisfied. Then for all v ∈ [0, T ) and large enough n, we have

E 0,x |Y v -Y n v | 2 + E 0,x |Z v -Z n v | 2 ≤ C 3.1 Ψ(x) 2 h 1 2 ∧α
with C 3.1 = C(b, σ, f, g, T, p 0 , δ) and Ψ is given in (61).

Remark 3.2. As noticed above, the filtration G k coincides with F τ k , for all k = 0, . . . , n. The expectation E 0,x appearing in Proposition 3.1 and in Theorem 3.1 is defined on the probability space (Ω, F , P).

Remark 3.3. In order to avoid too much notation for the dependencies of the constants, if for example only g is mentioned and not C g , this means that the estimate might depend also on the bounds of the derivatives of g.

From ( 24) one can see that the convergence rates stated in Proposition 3.1 and Theorem 3.1 are the natural ones for this approach. The results are proved in the next two sections. In both proofs, we will use the following remark.

Remark 3.4. Since the process (X t ) t≥0 is strong Markov we can express conditional expectations with the help of an independent copy of B denoted by B, for example

E τ k g(X n T ) = Ẽg( X τ k ,Xτ k τn ) for 0 ≤ k ≤ n, where X τ k ,Xτ k τn = X τ k + n j=k+1 b(t j , X τ k ,Xτ k τj-1 )h + n j=k+1 σ(t j , X τ k ,Xτ k τj-1 )( Bτ j-k -Bτ j-k-1 ), (25)
(we define τk := 0 and τj := inf{t > τj-1 :

| Bt -Bτj-1 | = √ h} for j ≥ 1 and τ n := τ k + τn-k for n ≥ k).
In fact, to represent the conditional expectations E t k and E τ k we work here with Ẽ and the Brownian motions B ′ and B ′′ , respectively, given by

B ′ t = B t∧t k + B(t-t k ) + and B ′′ t = B t∧τ k + B(t-τ k ) + , t ≥ 0. (26)

Proof of Proposition 3.1: the approximation rates for the zero generator case

To shorten the notation, we use E := E 0,x . Let us first deal with the error of

Y . If v belongs to [t k , t k+1 ) we have Y n v = Y n t k . Then E|Y v -Y n v | 2 ≤ 2(E|Y v -Y t k | 2 + E|Y t k -Y n t k | 2 ). Using Theorem 4.1 we bound Y v -Y t k by C y 4.1 Ψ(x)(v -t k ) 1 2 = C(C g , b, σ, T, p 0 , δ)Ψ(x)(v -t k ) 1 2
(since α = 1 can be chosen when g is locally Lipschitz continuous). It remains to bound

E|Y t k -Y n t k | 2 = E|E t k g(X T ) -E τ k g(X n T )| 2 = E| Ẽg( Xt k ,Xt k tn ) -Ẽg( X τ k ,Xτ k τn )| 2 .
By ( 5) and the Cauchy-Schwarz inequality (Ψ

1 := C g (1 + | Xt k ,Xt k tn | p0 + | X τ k ,Xτ k τn | p0 )), | Ẽg( Xt k ,Xt k tn ) -Ẽg( X τ k ,Xτ k τn )| 2 ≤ ( Ẽ(Ψ 1 | Xt k ,Xt k tn - X τ k ,Xτ k τn |)) 2 ≤ Ẽ(Ψ 2 1 ) Ẽ| Xt k ,Xt k tn - X τ k ,Xτ k τn | 2 .
Finally, we get by Lemma 5.2-(v) that

E|Y t k -Y n t k | 2 ≤ E Ẽ(Ψ 4 1 ) 1 2 E Ẽ| Xt k ,Xt k tn - X τ k ,Xτ k τn | 4 1 2 ≤ C(C g , b, σ, T, p 0 )Ψ(x) 2 h 1 2 .
Let us now deal with the error of Z. We use

Z v -Z n v ≤ Z v -Z t k + Z t k -Z n t k and the representation Z t = σ(t, X t ) Ẽ(g ′ ( Xt,Xt T )∇ Xt,Xt T ) (see Theorem 4.2), where Xt,x s = x + s t b(r, Xt,x r )dr + s t σ(r, Xt,x r )d Br-t , (27)
∇ Xt,x s = 1 + s t b x (r, Xt,x r )∇ Xt,x r dr + s t σ x (r, Xt,x r )∇ Xt,x r d Br-t , 0 ≤ t ≤ s ≤ T.
For the first term we get by the assumption on g and Lemma 5.2-(i) and (iii)

Z v -Z t k = σ(v, X v ) Ẽ(g ′ ( Xv,Xv T )∇ Xv,Xv T ) -σ(t k , X t k ) Ẽ(g ′ ( Xt k ,Xt k T )∇ Xt k ,Xt k T ) ≤ σ(v, X v ) -σ(t k , X t k ) 4 Ẽ(g ′ ( Xv,Xv T )∇ Xv,Xv T ) 4 + σ ∞ Ẽ(g ′ ( Xv,Xv T )∇ Xv,Xv T ) -Ẽ(g ′ ( Xt k ,Xt k T )∇ Xv,Xv T ) + σ ∞ Ẽ(g ′ ( Xt k ,Xt k T )∇ Xv,Xv T ) -Ẽ(g ′ ( Xt k ,Xt k T )∇ Xt k ,Xt k T ) ≤ C(C g ′ , b, σ, T, p 0 )Ψ(x) h 1 2 + X v -X t k 4 + E Ẽ| Xv,Xv T - Xt k ,Xt k T | 4α 1 4 + E Ẽ|∇ Xv,Xv T -∇ Xt k ,Xt k T | 4 1 4 ≤ C(C g ′ , b, σ, T, p 0 )Ψ(x)h α 2 .
We compute the second term using Z n t k as given in [START_REF] Cheridito | BS∆Es and BSDEs with non-Lipschitz drivers: Comparison, convergence and robustness[END_REF]. Hence, with the notation from Definition 2.2,

Z t k -Z n t k 2 = E σ(t k , X t k ) Ẽg ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn -ẼD n k+1 g( X τ k ,Xτ k τn ) 2 ≤ σ 2 ∞ E Ẽ(g ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn ) - ẼD n k+1 g( X τ k ,Xτ k τn ) σ(t k , X t k ) 2 = σ 2 ∞ E Ẽ(g ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn ) -Ẽ g (k+1,n+1) x D n k+1 X τ k ,Xτ k τn σ(t k , X t k ) 2 .
We insert ± Ẽ(g

(k+1,n+1) x ∇ Xt k ,Xt k tn
) and get by the Cauchy-Schwarz inequality that

Ẽ(g ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn ) -Ẽ g (k+1,n+1) x D n k+1 X τ k ,Xτ k τn σ(t k , X t k ) 2 ≤ 2 Ẽ|g ′ ( Xt k ,Xt k tn ) -g (k+1,n+1) x | 2 Ẽ|∇ Xt k ,Xt k tn | 2 + 2 Ẽ|g (k+1,n+1) x | 2 Ẽ ∇ Xt k ,Xt k tn - D n k+1 X τ k ,Xτ k τn σ(t k , X t k ) 2 . ( 28
)
For the estimate of Ẽ|∇ Xt k ,Xt k tn | 2 we use Lemma 5.2. Since g ′ satisfies (5) we proceed with

Ẽ|g ′ ( Xt k ,Xt k tn ) -g (k+1,n+1) x | 2 ≤ 1 0 Ẽ g ′ ( Xt k ,Xt k tn ) -g ′ (ϑT k+1,+ X τ k ,Xτ k τn + (1 -ϑ)T k+1,- X τ k ,Xτ k τn ) 2 dϑ ≤ 1 0 ( ẼΨ 4 1 ) 1 2 Ẽ Xt k ,Xt k tn -ϑT k+1,+ X τ k ,Xτ k τn -(1 -ϑ)T k+1,- X τ k ,Xτ k τn 4α 1 2 dϑ,
where

Ψ 1 := C g ′ (1 + | Xt k ,Xt k tn | p0 + |ϑT k+1,+ X τ k ,Xτ k τn + (1 -ϑ)T k+1,- X τ k ,Xτ k τn | p0 ). For ẼΨ 4 1 and Ẽ Xt k ,Xt k tn -(ϑT k+1,+ X τ k ,Xτ k τn + (1 -ϑ)T k+1,- X τ k ,Xτ k τn ) 4α ≤ 8 ϑ 2α Ẽ Xt k ,Xt k tn -T k+1,+ X τ k ,Xτ k τn 4α + (1 -ϑ) 2α Ẽ Xt k ,Xt k tn -T k+1,- X τ k ,Xτ k τn 4α ≤ C(b, σ, T )h 2α + C(b, σ, T )(|X t k -X τ k | 4α + h α ),
we use Lemma 5.4 and Lemma 5.2-(v). For the last term in [START_REF] Kruse | Lp-solution for BSDEs with jumps in the case p < 2[END_REF] we notice that

E Ẽ|g (k+1,n+1) x | 4 ≤ C(C g ′ , b, σ, T, p 0 )Ψ 4 (x). By Lemma 5.2 we have E Ẽ|∇ Xt k ,Xt k tn -∇ X τ k ,Xτ k τn | p ≤ C(b, σ, T, p)h p 4
, and by Lemma 5.4,

E Ẽ ∇ X τ k ,Xτ k τn - D n k+1 X τ k ,Xτ k τn σ(t k , X t k ) p ≤ C(p)E ∇X n,t k ,X n t k tn - D n k+1 X n tn σ(t k+1 , X n t k ) p + C(p)E D n k+1 X n tn σ(t k+1 , X n t k ) - D n k+1 X n tn σ(t k , X t k ) p ≤ C(b, σ, T, p, δ)h p 4 . Consequently, Z t k -Z n t k 2 ≤ C(C g ′ , b, σ, T, p 0 , δ)Ψ 2 (x)h α 2 .

Proof of Theorem 3.1: the approximation rates for the general case

Let u : [0, T ) × R → R be the solution of the PDE (37) associated to [START_REF] Alanko | Regression-based Monte Carlo methods for solving nonlinear PDEs[END_REF]. We use the representations Y s = u(s, X s ) and Z s = σ(s, X s )u x (s, X s ) stated in Theorem 4.2 and define

F (s, x) := f (s, x, u(s, x), σ(s, x)u x (s, x)). (29)
From ( 1) and ( 3) we conclude

Y t k -Y n t k ≤ E t k g(X T ) -E τ k g(X n T ) + E t k T t k f (s, X s , Y s , Z s )ds -hE τ k n-1 m=k f (t m+1 , X n tm , Y n tm , Z n tm ) ,
where Proposition 3.1 provides the estimate for the terminal condition. We decompose the generator term as follows:

E t k f (s, X s , Y s , Z s ) -E τ k f (t m+1 , X n tm , Y n tm , Z n tm ) = [E t k f (s, X s , Y s , Z s ) -E t k f (t m , X tm , Y tm , Z tm )] + [E t k F (t m , X tm ) -E τ k F (t m , X n tm )] +[E τ k F (t m , X n tm ) -E τ k F (t m , X tm )] + [E τ k f (t m , X tm , Y tm , Z tm ) -E τ k f (t m+1 , X n tm , Y n tm , Z n tm )] =: d 1 (s, m) + d 2 (m) + d 3 (m) + d 4 (m).
We use

E t k T t k f (s, X s , Y s , Z s )ds -hE τ k n-1 m=k f (t m+1 , X n tm , Y n tm , Z n tm ) ≤ n-1 m=k tm+1 tm d 1 (s, m)ds + h 4 i=2 d i (m)
and estimate the expressions on the right hand side. For the function F defined in [START_REF] Ma | Numerical method for backward stochastic differential equations[END_REF] we use Assumption 2.3 (which implies that (5) holds for α = 1) to derive by Theorem 4.2 and the mean value theorem that for

x 1 , x 2 ∈ R there exist ξ ∈ [min{x 1 , x 2 }, max{x 1 , x 2 }] such that |F (t, x 1 ) -F (t, x 2 )| = |f (t, x 1 , u(t, x 1 ), σ(t, x 1 )u x (t, x 1 )) -f (t, x 2 , u(t, x 2 ), σ(t, x 2 )u x (t, x 2 ))| ≤ C(L f , σ) 1 + c 2 4.2 Ψ(ξ) + c 3 4.2 Ψ(ξ) (T -t) 1 2 |x 1 -x 2 | ≤ C(L f , c 2,3 4.2 , σ, T )(1 + |x 1 | p0+1 + |x 2 | p0+1 ) |x 1 -x 2 | (T -t) 1 2 . ( 30
)
By [START_REF] Ph | Simulation of BSDEs by Wiener chaos expansion[END_REF], standard estimates on (X s ), Theorem 4.1-(i) and Proposition 4.1 for p = 2 we immediately get

d 1 (s, m) ≤ C(L f , C y 4.1 , C 4.1 , b, σ, T )Ψ(x) h 1 2 = C(b, σ, f, g, T, p 0 , δ)Ψ(x) h 1 2 .
For the estimate of d 2 one exploits

E t k F (t m , X tm ) -E τ k F (t m , X n tm ) = ẼF (t m , Xt k ,Xt k tm ) -ẼF (t m , Xn,t k ,X n t k tm )
and then uses [START_REF] Ma | Representation theorems for backward stochastic differential equations[END_REF] and Lemma 5.2-(v). This gives

d 2 (m) ≤ C(L f , c 2,3 4.2 , b, σ, T, p 0 )Ψ(x) 1 (T -t m ) 1 2 h 1 4 .
For d 3 we start with Jensen's inequality and continue then similarly as above to get

d 3 (m) ≤ F (t m , X n tm ) -F (t m , X tm ) ≤ C(L f , c 2,3 4.2 , b, σ, T, p 0 )Ψ(x) 1 (T -t m ) 1 2 h 1 4 ,
and for the last term we get

d 4 (m) ≤ L f (h 1 2 + X tm -X n tm + Y tm -Y n tm + Z tm -Z n tm ).
This implies

Y t k -Y n t k ≤ CΨ(x)h 1 4 + hL f n-1 m=k ( Y tm -Y n tm + Z tm -Z n tm ), (31)
where

C = C(L f , C y 3.1 , C y 4.1 , C 4.1 , c 2,3 4.2 , b, σ, T, p 0 ) = C(b, σ, f, g, T, p 0 , δ).
For Z t k -Z n t k we use the representations ( 13), ( 16) and the approximation [START_REF] Karoui | Backward stochastic differential equations in finance[END_REF] as well as Proposition 2.1. Instead of N n,t k tn we will use here the notation N n,τ k τn to indicate its measurability w.r.t. the filtration (F t ). It holds that

Z n t k -Z t k ≤ Z n t k -Ẑn t k + Z t k -Ẑn t k ≤ C 2.1 Ψ(x)h α 2 + σ(t k , X t k ) Ẽg ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn -ẼD n k+1 g( Xn,t k ,X n t k tn ) + E t k T t k+1 f (s, X s , Y s , Z s )N t k s ds σ(t k , X t k ) -E τ k h n-1 m=k+1 f (t m+1 , X n tm , Y n tm , Z n tm )N n,τ k τm σ(t k+1 , X n t k ) + E t k t k+1 t k f (s, X s , Y s , Z s )N t k s ds σ(t k , X t k ) . (32)
For the terminal condition Proposition 3.1 provides

σ(t k , X t k ) Ẽg ′ ( Xt k ,Xt k tn )∇ Xt k ,Xt k tn -ẼD n k+1 g( Xn,t k ,X n t k tn ) ≤ (C z 3.1 ) 1 2 Ψ(x)h 1 4 . ( 33
)
We continue with the generator terms and use F defined in [START_REF] Ma | Numerical method for backward stochastic differential equations[END_REF] to decompose the difference

E t k f (s, X s , Y s , Z s )N t k s σ(t k , X t k ) -E τ k f (t m+1 , X n tm , Y n tm , Z n tm )N n,τ k τm σ(t k+1 , X n t k ) = E t k f (s, X s , Y s , Z s )N t k s σ(t k , X t k ) -E t k f (t m , X tm , Y tm , Z tm )N t k tm σ(t k , X t k ) +E t k F (t m , X tm )N t k tm σ(t k , X t k ) -E τ k F (t m , X n tm )N n,τ k τm σ(t k+1 , X n t k ) +E τ k [F (t m , X n tm ) -F (t m , X tm )]N n,τ k τm σ(t k+1 , X n t k ) +E τ k [f (t m , X tm , Y tm , Z tm ) -f (t m+1 , X n tm , Y n tm , Z n tm )]N n,τ k τm σ(t k+1 , X n t k ) =: t 1 (s, m) + t 2 (m) + t 3 (m) + t 4 (m)
where s ∈ [t m , t m+1 ). For t 1 we use that

E t k f (t m , X t k , Y t k , Z t k )(N t k s -N t k tm ) = 0, so that t 1 (s, m) ≤ E t k f (s, X s , Y s , Z s )N t k s σ(t k , X t k ) -E t k f (t m , X tm , Y tm , Z tm )N t k s σ(t k , X t k ) + E t k (f (t m , X tm , Y tm , Z tm ) -f (t m , X t k , Y t k , Z t k ))(N t k s -N t k tm )σ(t k , X t k ) .
As before, we rewrite the conditional expectations with the help of the independent copy B. Then

E t k f (s, X s , Y s , Z s )N t k s -E t k f (t m , X tm , Y tm , Z tm )N t k s = Ẽ[(f (s, Xt k ,Xt k s , Ỹ t k ,Xt k s , Zt k ,Xt k s ) -f (t m , Xt k ,Xt k tm , Ỹ t k ,Xt k tm , Zt k ,Xt k tm )) Ñ t k s ]
and

E t k (f (t m , X tm , Y tm , Z tm ) -f (t m , X t k , Y t k , Z t k ))(N t k s -N t k tm ) = Ẽ[(f (t m , Xt k ,Xt k tm , Ỹ t k ,Xt k tm , Zt k ,Xt k tm ) -f (t m , X t k , Y t k , Z t k ))( Ñ t k s -Ñ t k tm )].
We apply the conditional Hölder inequality, and from the estimates [START_REF] Toldo | Stability of solutions of BSDEs with random terminal time[END_REF] and

Ẽ| Ñ t k s -Ñ t k tm | 2 ≤ C(b, σ, T, δ) h (s-t k ) 2 we get t 1 (s, m) ≤ κ 2 σ ∞ (s -t k ) 1 2 f (s, X s , Y s , Z s ) -f (t m , X tm , Y tm , Z tm ) +C(b, σ, T, δ) h 1 2 s -t k f (t m , X tm , Y tm , Z tm ) -f (t k , X t k , Y t k , Z t k ) ≤ C(L f , C y 4.1 , C 4.1 , κ 2 , b, σ, T, p 0 , δ)Ψ(x) h 1 2 (s -t k ) 1 2
, since for 0 ≤ t < s ≤ T we have by Theorem 4.1 and Proposition 4.1 that

f (s, X s , Y s , Z s ) -f (t, X t , Y t , Z t ) ≤ C(L f , C y 4.1 , C 4.1 , b, σ, T, p 0 )Ψ(x)(s -t) 1 2 . ( 34
)
For the estimate of t 2 Lemma 5.2, Lemma 5.3, ( 30) and (36) yield

t 2 (m) = ẼF (t m , Xt k ,Xt k tm ) Ñ t k tm σ(t k , X t k ) -ẼF (t m , X τ k ,Xτ k τm ) Ñ n,τ k τm σ(t k+1 , X τ k ) ≤ C(κ 2 , σ) (t m -t k ) 1 2 E Ẽ(F (t m , Xt k ,Xt k tm ) -F (t m , X τ k ,Xτ k τm )) 2 1 2 +(E Ẽ|F (t m , X τ k ,Xτ k τm ) -F (t m , X τ k )| 2 Ẽ| Ñ t k tm σ(t k , X t k ) -Ñ n,τ k τm σ(t k+1 , X τ k )| 2 ) 1 2 ≤ C(L f , c 2,3 4.2 , κ 2 , b, σ, T, p 0 , δ) Ψ(x) (T -t m ) 1 2 h 1 4 (t m -t k ) 1 2
.

For t 3 we use the conditional Hölder inequality, (30), [START_REF] Delarue | A forward-backward stochastic algorithm for quasi-linear PDEs[END_REF] and Lemma 5.2:

t 3 (m) = E τ k [F (t m , X n tm ) -F (t m , X tm )]N n,τ k τm σ(t k+1 , X τ k ) ≤ C( κ 2 , σ) (t m -t k ) 1 2 F (t m , X n tm ) -F (t m , X tm ) ≤ C(L f , c 2,3 4.2 , b, σ, T, p 0 , δ) Ψ(x) (T -t m ) 1 2 h 1 4 (t m -t k ) 1 2
.

The term t 4 can be estimated as follows:

t 4 (m) = E τ k [f (t m , X tm , Y tm , Z tm ) -f (t m+1 , X n tm , Y n tm , Z n tm )]N n,τ k τm σ(t k+1 , X τ k ) ≤ C(L f , b, σ, T, δ) (t m -t k ) 1 2
(h

1 2 + X tm -X n tm + Y tm -Y n tm + Z tm -Z n tm ).
Finally, for the remaining term of the estimate of Z t k -Z n t k , we use [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings-With Normal Martingales[END_REF] and [START_REF] Toldo | Stability of solutions of BSDEs with random terminal time[END_REF] to get

E t k f (s, X s , Y s , Z s )N t k s σ(t k , X t k ) = E t k [(f (s, X s , Y s , Z s ) -f (s, X t k , Y t k , Z t k ))N t k s ] σ(t k , X t k ) ≤ C(L f , C y 4.1 , C 4.1 , κ 2 , b, σ, T, p 0 )Ψ(x).
Consequently, from ( 32), [START_REF] Peng | Numerical algorithms for backward stochastic differential equations with 1-d Brownian motion: convergence and simulations[END_REF], the estimates for the remaining term and for t 1 , ..., t 4 it follows that

Z t k -Z n t k ≤ C 2.1 Ψ(x)h α 2 + (C z 3.1 ) 1 2 Ψ(x)h 1 4 + C(L f , C y 4.1 , C 4.1 , b, σ, T, p 0 , κ 2 )Ψ(x)h +C(L f , C y 4.1 , C 4.1 , κ 2 , b, σ, T, p 0 , δ)Ψ(x)h 1 2 T t k ds (s -t k ) 1 2 +C(L f , c 2,3 4.2 , κ 2 , b, σ, T, p 0 , δ)h n-1 m=k+1 Ψ(x) (T -t m ) 1 2 h 1 4 (t m -t k ) 1 2 +C(L f , b, σ, T, δ)h n-1 m=k+1 ( Y tm -Y n tm + Z tm -Z n tm ) 1 (t m -t k ) 1 2 ≤ C(C 2.1 , C z 3.1 ) Ψ(x)h α 2 ∧ 1 4 + C(L f , c 2,3 4.2 , C y 4.1 , C 4.1 , κ 2 , b, σ, T, p 0 , δ)Ψ(x)h 1 4 +C(L f , b, σ, T, δ) n-1 m=k+1 ( Y tm -Y n tm + Z tm -Z n tm ) 1 (t m -t k ) 1 2
h.

Then we use [START_REF] Martínez | Numerical Method for reflected backward stochastic differential equations[END_REF] and the above estimate to get

Y t k -Y n t k + Z t k -Z n t k ≤ C(C 2.1 , C z 3.1 ) Ψ(x)h α 2 ∧ 1 4 + C(L f , C y 3.1 , C y 4.1 , C 4.1 , c 2,3 4.2 , κ 2 , b, σ, T, p 0 , δ)Ψ(x)h 1 4 +C(L f , b, σ, T, δ) n-1 m=k+1 ( Y tm -Y n tm + Z tm -Z n tm ) 1 (t m -t k ) 1 2 h.
Consequently, summarizing the dependencies, there is a C = C(b, σ, f, g, T, p 0 , δ) such that

Y t k -Y n t k + Z t k -Z n t k ≤ C Ψ(x)h α 2 ∧ 1 4 .
By Theorem 4.1 (note that by Assumption 2.3 on g we have α = 1) it follows that

Y v -Y n v ≤ Y v -Y t k + Y t k -Y n t k ≤ C y 4.1 Ψ(x)h 1 2 + Ψ(x)h α 2 ∧ 1 4 .
while Proposition 4.1 implies that

Z v -Z t k ≤ C 4.1 Ψ(x)h 1 2
, and hence we have

E 0,x |Y v -Y n v | 2 + E 0,x |Z v -Z n v | 2 ≤ C 3.1 Ψ(x) 2 h 1 2 ∧α with C 3.1 = C 3.1 (b, σ, f, g, T, p 0 , δ).
4. Some properties of solutions to BSDEs and their associated PDEs

Malliavin weights

We use the SDE from (1) started in (t, x),

X t,x s = x + s t b(r, X t,x r )dr + s t σ(r, X t,x r )dB r , 0 ≤ t ≤ s ≤ T (35)
G(t, x) := EH(X t,x T ) implies that G ∈ C 1,2 ([0, T ) × R). Especially it holds for 0 ≤ t ≤ r < T that ∂ x G(r, X t,x r ) = E[H(X t,x T )N r,(t,x) T |F t r ],
where

(F t r ) r∈[t,T ] is the augmented natural filtration of (B t,0 r ) r∈[t,T ] , N r,(t,x) T = 1 T -r T r ∇X t,x s σ(s, X t,x s )∇X t,x r dB s ,
and ∇X t,x s is given in [START_REF] Chassagneux | Numerical Stability Analysis of the Euler Scheme for BSDEs[END_REF]. Moreover, for q ∈ (0, ∞) there exists a κ q > 0 such that a.s.

(E[|N r,(t,x) T | q |F t r ]) 1 q ≤ κ q (T -r) 1 2 and E[N r,(t,x) T |F t r ] = 0 a.s. ( 36
)
and we have

∂ x G(r, X t,x r ) Lp(P) ≤ κ q H(X t,x T ) -E[H(X t,x T )|F t r ] p √ T -r for 1 < q, p < ∞ with 1 p + 1 q = 1.

Regularity of solutions to BSDEs

The following result originates from [START_REF] Geiss | Generalized fractional smoothness and Lp-variation of BSDEs with non-Lipschitz terminal conditions[END_REF]Theorem 1] where also path dependent cases were included. We formulate it only for our Markovian setting but use P t,x since we are interested in an estimate for all (t, x) ∈ [0, T ) × R. A sketch of a proof of this formulation can be found in [START_REF] Geiss | Random walk approximation of BSDEs with Hölder continuous terminal condition[END_REF]. (i) There exists a constant C y 4.1 > 0 such that for 0 ≤ t < s ≤ T and x ∈ R,

Y s -Y t Lp(Pt,x) ≤ C y 4.1 Ψ(x) s t (T -r) α-1 dr 1 2
, (ii) there exists a constant C z 4.1 > 0 such that for 0 ≤ t < s < T and x ∈ R,

Z s -Z t Lp(Pt,x) ≤ C z 4.1 Ψ(x) s t (T -r) α-2 dr 1 2
.

The constants C y 4.1 and C z 4.1 depend on (L f , K f , C g , c 1,2 4.2 , κ q , b, σ, T, p 0 , p), and Ψ(x) is defined in (7).

Properties of the associated PDE

The theorem below collects properties of the solution to the PDE associated to the FBSDE (1).

For a proof see [42, Theorem 3.2], [START_REF] Zhang | Some fine properties of backward stochastic differential equations, with applications[END_REF]

         u t (t, x) + σ 2 (t,x) 2 u xx (t, x) + b(t, x)u x (t, x) + f (t, x, u(t, x), σ(t, x)u x (t, x)) = 0, t ∈ [0, T ), x ∈ R, u(T, x) = g(x), x ∈ R (37) we have (i) Y t = u(t, X t ) a.s., where u(t, x) = E t,x g(X T ) + T t f (r, X r , Y r , Z r )dr and |u(t, x)| ≤ c 1
4.2 Ψ(x) with Ψ given in [START_REF] Bouchard | Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations[END_REF], where c 1 4.2 depends on L f , K f , C g , T, p 0 and on the bounds and Lipschitz constants of b and σ.

(ii) (a) ∂ x u exists and is continuous in

[0, T ) × R, (b) Z t,x s = u x (s, X t,x s )σ(s, X t,x s ) a.s., (c) |u x (t, x)| ≤ c 2 4.2 Ψ(x) (T -t) 1-α 2
, where c 2 4.2 depends on L f , K f , C g , T, p 0 , κ 2 = κ 2 (b, σ, T, δ) and on the bounds and Lipschitz constants of b and σ, and hence c 2 4.2 = c 2 4.2 (L f , K f , C g , b, σ, T, p 0 , δ).

(iii) (a) ∂ 2 x u exists and is continuous in [0, T ) × R, (b) |∂ 2 x u(t, x)| ≤ c 3 4.2 Ψ(x) (T -t)
0 ≤ t < s ≤ T and x ∈ R, Z s -Z t Lp(Pt,x) ≤ C 4.1 Ψ(x)(s -t) 1 2
, where C 4.1 depends on c 2,3 4.2 , b, σ, f, g, T, p 0 , p, and hence C 4.1 = C 4.1 (b, σ, f, g, T, p 0 , p, δ).

Proof. From Z t,x s = u x (s, X t,x s )σ(s, X t,x s ) and ∇Y t,x s = ∂ x u(s, X t,x s ) = u x (s, X t,x s )∇X t,x s we conclude

Z t,x s = ∇Y t,x s ∇X t,x s σ(s, X t,x s ), 0 ≤ t ≤ s ≤ T. (38)
It is well-known (see e.g. [START_REF] Karoui | Backward stochastic differential equations in finance[END_REF]) that the solution ∇Y of the linear BSDE

∇Y s = g ′ (X T )∇X T + T s f x (Θ r )∇X r + f y (Θ r )∇Y r + f z (Θ r )∇Z r dr - T s ∇Z r dB r , 0 ≤ s ≤ T, (39)
can be represented as

∇Y s ∇X s = E s g ′ (X T )∇X T Γ s T + T s f x (Θ r )∇X r Γ s r dr 1 ∇X s = Ẽ g ′ ( Xs,Xs
where Θ r := (r, X r , Y r , Z r ) and Γ s denotes the adjoint process given by

Γ s r = 1 + r s f y (Θ u )Γ s u du + r s f z (Θ u )Γ s u dB u , s ≤ r ≤ T, and
Γt,x s = 1 + s t f y ( Θt,x r ) Γt,x r dr + s t f z ( Θt,x r ) Γt,x r d Br , t ≤ s ≤ T, x ∈ R
where B denotes an independent copy of B. Notice that ∇X t,x t = 1, so that

∇Y t,x t ∇X t,x t = ∇Y t,x t = Ẽ g ′ ( Xt,x T )∇ Xt,x T Γt,x T + T t f x ( Θt,x r )∇ Xt,x r Γt,x r dr .
Then, by [START_REF] Yao | Lp Solutions of Backward Stochastic Differential Equations with Jumps[END_REF],

Z s -Z t Lp(Pt,x) ≤ C(σ) ∇Y s ∇X s - ∇Y t ∇X t Lp(Pt,x) + ∇Y t L2p(Pt,x) [(s -t) 1 2 + X t,x s -x L2p(Pt,x) ] .
Since (∇Y s , ∇Z s ) is the solution to the linear BSDE [START_REF] Walsh | The rate of convergence of the binomial tree scheme[END_REF] with bounded f x , f y , f z , we have that

∇Y t L2p(Pt,x) ≤ C(b, σ, f, g, T, p). Obviously, X t,x s -x L2p(Pt,x) ≤ C(b, σ, T, p)(s -t) 1 2 . So it remains to show that ∇Y s ∇X s - ∇Y t ∇X t Lp(Pt,x) ≤ CΨ(x)(s -t) 1 2 .
We intend to use (40) in the following. There is a certain degree of freedom how to connect B and B in order to compute conditional expectations. Here, unlike in [START_REF] Henry-Labordere | A numerical algorithm for a class of BSDEs via the branching process[END_REF], we define the processes

B ′ u = B u∧s + Bu∨s -Bs and B ′′ u = B u∧t + Bu∨t -Bt , u ≥ 0
as driving Brownian motions for ∇Ys ∇Xs and ∇Yt ∇Xt , respectively. This will especially simplify the estimate for Ẽ| Γs,Xs T -Γt,x T | q below. From the above relations we get for (X s := X t,x s )

∇Y s ∇X s - ∇Y t ∇X t Lp(Pt,x) ≤ Ẽ g ′ ( Xs,Xs T )∇ Xs,Xs T Γs,Xs T -g ′ ( Xt,x T )∇ Xt,x T Γt,x T p + s t Ẽ f x ( Θt,x r )∇ Xt,x r Γt,x r p dr + T s Ẽ f x ( Θs,Xs r )∇ Xs,Xs r Γs,Xs r -f x ( Θt,x r )∇ Xt,x r Γt,x r dr p =: J 1 + J 2 + J 3 .
Since g ′ is Lipschitz continuous and of polynomial growth, the estimate

J 1 ≤ C(b, σ, g, T, p)Ψ(x)(s- t) 1 2
follows by Hölder's inequality and the L q -boundedness for any q > 0 of all the factors, as well as from the estimates for Xs,Xs Since f y and f z are bounded we have Ẽ| Γs,Xs r | q + Ẽ| Γt,x r | q ≤ C(f, T, q). Similar to [START_REF] Ma | Representation theorems for backward stochastic differential equations[END_REF], since f x , f y , f z are Lipschitz continuous w.r.t. the space variables, ))

-Γt,x T | q ≤ C(T, q) (s -t) q-1 Ẽ
-f x (r, Xt,x r , u(r, Xt,x r ), σ(r, Xt,x r )u x (r, Xt,x r ))| ≤ C(c 2,3 4.2 , σ, f, T )(1 + | Xs,Xs r | p0+1 + | Xt,x r | p0+1 ) | Xs,Xs r -Xt,x r | (T -r) 1 2 , so that Lemma 5.2 yields Ẽ|f x ( Θs,Xs r ) -f x ( Θt,x r )| q ≤ C(c 2,3 4.2 , b, σ, f, T, p 0 , q)(1 + |X s | p0+1 + |x| p0+1 ) q |X s -x| q + |s -t| q 2 (T -r) 1 2
.

The same holds for |f y ( Θs,Xs for p > 0.

For J 2 ≤ C(ts) it is enough to realise that the integrand is bounded. The estimate for J 3 follows similarly to that of J 1 .

Properties of the solution to the finite difference equation

Recall the definition of D n m given in [START_REF] Chassagneux | Cubature methods to solve BSDEs: Error expansion and complexity control[END_REF]. By (4),

X n,tm,x tm+1 = x + hb(t m+1 , x) + √ hσ(t m+1 , x)ε m+1 , (41)
so that

T m+1,± u n (t m+1 , X n,tm,x tm+1 ) = u n (t m+1 , x + hb(t m+1 , x) ± √ hσ(t m+1 , x)). ( 42
)
While for the solution to the PDE (37) one can observe in Theorem 4.2 the well-known smoothing property which implies that u is differentiable on [0, T )×R even though g is only Hölder continuous, in following proposition, for the solution u n to the finite difference equation we have to require from g the same regularity as we want for u n .

Proposition 4.2. Let Assumption 2.3 hold and assume that u n is a solution of

u n (t m , x) -hf (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1 )) = 1 2 [T m+1,+ u n (t m+1 , X n,tm,x tm+1 ) + T m+1,-u n (t m+1 , X n,tm,x tm+1 )], m = 0, . . . , n -1, ( 43
)
with terminal condition u n (t n , x) = g(x). Then, for sufficiently small h, the map x → u n (t m , x) is C 2 , and it holds

|u n (t m , x)| + |u n x (t m , x)| ≤ C u n ,1 Ψ(x), |u n xx (t m , x)| ≤ C u n ,2 Ψ 2 (x)
and

|u n xx (t m , x) -u n xx (t m , x)| ≤ C u n ,3 (1 + |x| 6p0+7 + |x| 6p0+7 )|x -x| α , ( 44
)
uniformly in m = 0, . . . , n -1. The constants C u n ,1 , C u n ,2 and C u n ,3 depend on the bounds of f, g, b, σ and their derivatives and on T and p 0 .

Proof.

Step 1. From ( 43), since g is C 2 and f y is bounded, for sufficiently small h we conclude by induction (backwards in time) that u n x (t m , x) exists for m = 0, ..., n -1, and that it holds

u n x (t m , x) = hf x (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1 )) +hf y (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1 )) u n x (t m , x) +hf z (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1 )) ∂ x D n m+1 u n (t m+1 , X n,tm,x tm+1 ) + 1 2 ∂ x T m+1,+ u n (t m+1 , X n,tm,x tm+1 ) + ∂ x T m+1,-u n (t m+1 , X n,tm,x tm+1 ) .
Similarly one can show that u n xx (t m , x) exists and solves the derivative of the previous equation.

Step 2. As stated in the proof of Proposition 2.1, the finite difference equation ( 43) is the associated equation to [START_REF] Bender | Time discretization and Markovian iteration for coupled FBSDEs[END_REF] in the sense that we have the representations [START_REF] Geiss | Generalized fractional smoothness and Lp-variation of BSDEs with non-Lipschitz terminal conditions[END_REF]. We will use that

u n (t m , x) = Y n,tm,x tm
and exploit the BSDE

Y n,tm,x tm = g(X n,tm,x T ) + (tm,T ] f (s, X n,tm,x s- , Y n,tm,x s- , Z n,tm,x s- )d[B n ] s - (tm,T ] Z n,tm,x s- dB n s , (45)
where we will drop the superscript t m , x from now on. For u n x (t m , x) we will consider

∇Y n tm := ∂ x Y n tm = g ′ (X n T )∂ x X n T + (tm,T ] f x ∂ x X n s-+ f y ∂ x Y n s-+ f z ∂ x Z n s-d[B n ] s - (tm,T ] ∂ x Z n s-dB n s . ( 46
)
Similarly as in the proof of [START_REF] Ma | Representation theorems for backward stochastic differential equations[END_REF]Theorem 3.1] the BSDE (46) can be derived from (45) as a limit of difference quotients w.r.t. x. Notice that the generator of ( 46) is random but has the same Lipschitz constant and linear growth bound as f. Assumption 2.3 allows us to find a p 0 ≥ 0 and a K > 0 such that

|g(x)| + |g ′ (x)| + |g ′′ (x)| ≤ K(1 + |x| p0+1 ) = Ψ(x).
In order to get estimates simultaneously for ( 45) and ( 46) we show the following lemma.

Lemma 4.2. We fix n and assume a BSDE

Y t k = ξ n + (t k ,T ] f(s, X s-, Y s-, Z s-)d[B n ] s - (t k ,T ] Z s-dB n s , m ≤ k ≤ n, ( 47
)
with ξ n = g(X n,tm,x T ) or ξ n = g ′ (X n,tm,x T )∂ x X n,tm,x T and X s := X n,tm,x s or X s := ∂ x X n,tm,x s such that f : Ω × [0, T ] × R 3 → R is measurable and satisfies |f(ω, t, x, y, z) -f(ω, t, x ′ , y ′ , z ′ )| ≤ L f (|x -x ′ | + |y -y ′ | + |z -z ′ |), |f(ω, t, x, y, z)| ≤ (K f + L f )(1 + |x| + |y| + |z|). (48)
Then for any p ≥ 2,

(i) E|Y t k | p + γp 4 E (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s ≤ CΨ p (x), for k = m, .
.., n and some γ p > 0,

(ii) E sup tm<s≤T |Y s-| p ≤ CΨ p (x), (iii) E (tm,T ] |Z s-| 2 d[B n ] s p 2 ≤ CΨ p (x),
for some constant C = C(b, σ, f, g, T, p, p 0 ).

Proof. (i) By Itô's formula (see [START_REF] Jacod | Limit theorems for stochastic processes[END_REF]Theorem 4.57]) we get for p ≥ 2

|Y t k | p = |ξ n | p -p (t k ,T ] Y s-|Y s-| p-2 Z s-dB n s + p (t k ,T ] Y s-|Y s-| p-2 f(s, X s-, Y s-, Z s-)d[B n ] s - s∈(t k ,T ] [|Y s | p -|Y s-| p -pY s-|Y s-| p-2 (Y s -Y s-)]. (49)
Following the proof of [27, Proposition 2] (which is carried out there in the Lévy process setting but can be done also for martingales with jumps, like B n ) we can use the estimate

- s∈(t k ,T ] [|Y s | p -|Y s-| p -pY s-|Y s-| p-2 (Y s -Y s-)] ≤ -γ p s∈(t k ,T ] |Y s-| p-2 (Y s -Y s-) 2
where γ p > 0 is computed in [START_REF] Yao | Lp Solutions of Backward Stochastic Differential Equations with Jumps[END_REF]Lemma A4]. Since

Y t ℓ+1 -Y t ℓ+1 -= f(t ℓ+1 , X t ℓ , Y t ℓ , Z t ℓ )h -Z t ℓ √ hε ℓ+1
we have

- s∈(t k ,T ] [|Y s | p -|Y s-| p -pY s-|Y s-| p-2 (Y s -Y s-)] ≤ -γ p n-1 ℓ=k |Y t ℓ | p-2 f(t ℓ+1 , X t ℓ , Y t ℓ , Z t ℓ )h -Z t ℓ √ hε ℓ+1 2 = -γ p h (t k ,T ] |Y s-| p-2 f 2 (s, X s-, Y s-, Z s-)d[B n ] s -γ p (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s +2γ p (t k ,T ] |Y s-| p-2 f(s, X s-, Y s-, Z s-)Z s-(B n s -B n s-)d[B n ] s .
Hence we get from (49)

|Y t k | p ≤ |ξ n | p -p (t k ,T ] Y s-|Y s-| p-2 Z s-dB n s + p (t k ,T ] Y s-|Y s-| p-2 f(s, X s-, Y s-, Z s-)d[B n ] s -γ p (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s +2γ p (t k ,T ] |Y s-| p-2 f(s, X s-, Y s-, Z s-)Z s-(B n s -B n s-)d[B n ] s .
From Young's inequality and (48) we conclude that there is a

c ′ = c ′ (p, K f , L f , γ p ) > 0 such that p|Y s-| p-1 |f(s, X s-, Y s-, Z s-)| ≤ γp 4 |Y s-| p-2 |Z s-| 2 + c ′ (1 + |X s-| p + |Y s-| p ),
and for

√ h < 1 8(L f +K f ) we find a c ′′ = c ′′ (p, L f , K f , γ p ) > 0 such that 2γ p √ h|Y s-| p-2 |f(s, X s-, Y s-, Z s-)||Z s-| ≤ γp 4 |Y s-| p-2 |Z s-| 2 + c ′′ (1 + |X s-| p + |Y s-| p ).
Then for c = c ′ + c ′′ we have

|Y t k | p ≤ |ξ n | p -p (t k ,T ] Y s-|Y s-| p-2 Z s-dB n s + c (t k ,T ] 1 + |X s-| p + |Y s-| p d[B n ] s - γp 2 (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s . (50)
By standard methods, approximating the terminal condition and the generator by bounded functions, it follows that for any a > 0

E sup t k ≤s≤T |Y s | a < ∞ and E (t k ,T ] |Z s-| 2 d[B n ] s a 2
< ∞.

Hence (t k ,T ] Y s-|Y s-| p-2 Z s-dB n
s has expectation zero. Taking the expectation in (50) yields

E|Y t k | p + γp 2 E (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s ≤ E|ξ n | p + cE (t k ,T ] 1 + |X s-| p + |Y s-| p d[B n ] s . (51) Since E|ξ n | p and E (t k ,T ] 1 + |X s-| p d[B n ] s are polynomially bounded in x, Gronwall's lemma gives Y t k p ≤ C(b, σ, f, g, T, p, p 0 )(1 + |x| p0+1 ), k = m, ..., n,
and inserting this into (51) yields

E (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s 1 p ≤ C(b, σ, f, g, T, p, p 0 )(1 + |x| p0+1 ), k = m, ..., n -1.
(ii) From (50) we derive by the inequality of BDG and Young's inequality that for

t m ≤ t k ≤ T E sup t k <s≤T |Y s-| p ≤ E|ξ n | p + C(p)E (t k ,T ] |Y s-| 2p-2 |Z s-| 2 d[B n ] s 1 2 + cE (t k ,T ] 1 + |X s-| p + |Y s-| p d[B n ] s ≤ E|ξ n | p + cE (t k ,T ] 1 + |X s-| p d[B n ] s + C(p)E   sup t k <s≤T |Y s-| p 2 (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s 1 2   +cE (t k ,T ] |Y s-| p d[B n ] s ≤ E|ξ n | p + cE (t k ,T ] 1 + |X s-| p d[B n ] s + C(p)E (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s +E sup t k <s≤T |Y s-| p ( 1 4 + c(T -t k )).
We assume that h is sufficiently small so that we find a t k with c(Tt k ) < 1 4 . We rearrange the inequality to have E sup t k <s≤T |Y s-| p on the l.h.s., and from (i) we conclude that

E sup t k <s≤T |Y s-| p ≤ 2E|ξ n | p + 2cE (t k ,T ] 1 + |X s-| p d[B n ] s + 2C(p)E (t k ,T ] |Y s-| p-2 |Z s-| 2 d[B n ] s ≤ C(b, σ, f, g, T, p, p 0 )(1 + |x| (p0+1)p ).

Now we may repeat the above step for

E sup t ℓ <s≤t k |Y s-| p with c(t k -t ℓ ) < 1
4 and ξ n = Y T replaced by Y t k , and continue doing so until we eventually get assertion (ii).

(iii) We proceed from (47), sup

k≤ℓ≤n (t ℓ ,T ] Z s-dB n s p ≤ C(p) |ξ n | p + sup k≤ℓ≤n |Y t ℓ | p + (t k ,T ] |f(s, X s-, Y s-, Z s-)| d[B n ] s p
, so that by (48) and the inequalities of BDG and Hölder we have that

E (t k ,T ] |Z s-| 2 d[B n ] s p 2 ≤ C(p) E|ξ n | p + E sup k≤ℓ≤n |Y t ℓ | p + C(p, L f , K f )E (t k ,T ] 1 + |X s-| + |Y s-|d[B n ] s p +C(p, L f , K f )(T -t k ) p 2 E (t k ,T ] |Z s-| 2 d[B n ] s p 2 . Hence for C(p, L f , K f )(T -t k ) p 2 < 1 2
we derive from assertion (ii) and from the growth properties of the other terms that

E (t k ,T ] |Z s-| 2 d[B n ] s p 2 ≤ C(b, σ, f, g, T, p, p 0 )(1 + |x| (p0+1)p ). ( 52
)
Repeating this procedure eventually yields (iii).

Step 3. Applying Lemma 4.2 to (45) and ( 46) we see that for all m = 0, ..., n we have

|u n (t m , x)| = |Y n,tm,x tm | = (E(Y n,tm,x tm ) 2 ) 1 2 ≤ C(b, σ, f, g, T, p 0 )(1 + |x| p0+1 )
and

|u n x (t m , x)| = (E(∂ x Y n,tm,x tm ) 2 ) 1 2 ≤ C(b, σ, f, g, T, p 0 )(1 + |x| p0+1 ). ( 53
)
Our next aim is to show that u n xx (t m , x) is locally Lipschitz in x. We first show that u n xx (t m , x) has polynomial growth. We introduce the BSDE which describes u n xx (t m , x) and denote for simplicity

f (t, x 1 , x 2 , x 3 ) := f (t, x, y, z) and D a := ∂ i1 x1 ∂ i2 x2 ∂ i3 x3 with a := (i 1 , i 2 , i 3 )
and consider

∂ 2 x Y n tm = g ′′ (X n T )(∂ x X n T ) 2 + g ′ (X n T )∂ 2 x X n T + (tm,T ] a∈{0,1,2} 3 i1+i2+i3=2 (D a f )(s, X n s-, Y n s-, Z n s-)(∂ x X n s-) i1 (∂ x Y n s-) i2 (∂ x Z n s-) i3 d[B n ] s + (tm,T ] a∈{0,1} 3 i1+i2+i3=1 (D a f )(s, X n s-, Y n s-, Z n s-)(∂ 2 x X n s-) i1 (∂ 2 x Y n s-) i2 (∂ 2 x Z n s-) i3 d[B n ] s - (tm,T ] ∂ 2 x Z n s-dB n s . (54)
We denote the generator of this BSDE by f and notice that it is of the structure f (ω, t, x, y, z) = f 0 (ω, t) + f 1 (ω, t)x + f 2 (ω, t)y + f 3 (ω, t)z.

Here f 0 (ω, t) denotes the integrand of the first integral on the r.h.s of (54), and from the previous

results one concludes that E( (tm,T ] |f 0 (s-)|d[B n ] s ) p < ∞. The functions f 1 (t) = (D (1,0,0) f )(t, •) = (∂ x f )(t, •) as well as f 2 (t) = (∂ y f )(t, •) and f 3 (t) = (∂ z f )(t,
•) are bounded by our assumptions.

We put

ξn := g ′′ (X n T )(∂ x X n T ) 2 + g ′ (X n T )∂ 2 x X n T .
Denoting the solution by ( Ŷ, Ẑ) we get for

C(f 3 )(T -t m ) ≤ 1 2 that E| Ŷtm | 2 + 1 2 E (tm,T ] | Ẑs-| 2 d[B n ] s ≤ C E| ξn | 2 + E (tm,T ] |f 0 (s-)|d[B n ] s 2 + E (tm,T ] | Xs-| 2 + | Ŷs-| 2 d[B n ] s . (55)
Now we derive the polynomial growth E| ξn | 2 ≤ CΨ 2 (x) from the properties of g ′ and g ′′ and from the fact that E sup tm<s≤T |∂ j x X n s | p is bounded for j = 1, 2 under our assumptions. Then the estimate

E (tm,T ] |f 0 (s-)|d[B n ] s 2 ≤ CΨ 4 (x)
can be derived from Lemma 4.2(ii)-(iii), so that Gronwall's lemma implies

| Ŷtm,x tm | = |u xx (t m , x)| ≤ CΨ 2 (x). ( 56
)
Finally, to show (44), one uses (54) and derives an inequality as in (55) but now for the difference

∂ 2 x Y n,tm,x tm -∂ 2 x Y n,tm,x tm .
Before proving it, let us state the following lemma.

Lemma 4.3. Let Assumption 2.3 hold. We have

E sup s |Z n,tm,x s- -Z n,tm,x s- | p 1/p ≤ C(Ψ(x) 2 + Ψ(x) 2 )|x -x|, p ≥ 2, (57)
E (tm,T ] |∂ x Z n,tm,x s- -∂ x Z n,tm,x s- | 2 d[B n ] s p 2 ≤ C(Ψ 4p (x) + Ψ 4p (x))|x -x| p , p ≥ 2, (58)
E (tm,T ] |∂ 2 x Z n,tm,x s- | 2 d[B n ] s p 2 ≤ CΨ 4p (x), p ≥ 2, ( 59
)
for some constant C = C(b, σ, f, g, T, p, p 0 ).

Proof of Lemma 4.3. (57): Introduce G(t k+1 , x) := D n k+1 u n (t k+1 , X n,t k ,x t k+1 ). Using relations (41)- [START_REF] Zhang | Representation of solutions to BSDEs associated with a degenerate FSDE[END_REF] and the bounds (53) and (56) for u n

x and u n xx , respectively, one obtains

|G(t k+1 , x) -G(t k+1 , x)| ≤ C(1 + |x| 2(p0+1) + |x| 2(p0+1) )|x -x|, x, x ∈ R, uniformly in t k+1 . Since Z n,tm,x t k = D n k+1 u n (t k+1 , X n,t k ,η t k+1 ) = G(t k+1 , η) where η = X n,tm,x t k
, the previous bound yields

|Z n,tm,x t k -Z n,tm,x t k | ≤ C(1 + |X n,tm,x t k | 2(p0+1) + |X n,tm,x t k | 2(p0+1) )|X n,tm,x t k -X n,
|f tm,x 0 (s-) -f tm,x 0 (s-)|d[B n ] s 2 ≤ C(Ψ 10 (x) + Ψ 10 (x))(1 + |x| 2 + |x| 2 )|x -x| 2α ,
we check the terms with the highest polynomial growth. For example, we have to deal with terms like E (tm,T ] |Z n,tm,x s-

-Z n,tm,x s- | |∂ x Z n,tm,x s- | 2 d[B n ] s 2 and E (tm,T ] |∂ x Z n,tm,x s- | 2 -|∂ x Z n,tm,x s- | 2 d[B n ] s 2 .
We bound the first term by using ( 52) and ( 57)

E (tm,T ] |Z n,tm,x s- -Z n,tm,x s- | |∂ x Z n,tm,x s- | 2 d[B n ] s 2 ≤ (E sup s |Z n,tm,x s- -Z n,tm,x s- | 4 ) 1 2 E (tm,T ] |∂ x Z n,tm,x s- | 2 d[B n ] s 4 1 2 ≤ C(Ψ 4 (x) + Ψ 4 (x))|x -x| 2 Ψ 4 (x).
We bound the second term by using ( 52) and ( 58)

E (tm,T ] |∂ x Z n,tm,x s- | 2 -|∂ x Z n,tm,x s- | 2 d[B n ] s 2 ≤ CE (tm,T ] |∂ x Z n,tm,x s- | 2 + |∂ x Z n,tm,x s- | 2 d[B n ] s (tm,T ] |∂ x Z n,tm,x s- -∂ x Z n,tm,x s- | 2 d[B n ] s ≤ C(Ψ 2 (x) + Ψ 2 (x))(Ψ 8 (x) + Ψ 8 (x))|x -x| 2 ≤ C(Ψ 10 (x) + Ψ 10 (x))(|x| 2-2α + |x| 2-2α )|x -x| 2α ≤ C(Ψ 10 (x) + Ψ 10 (x))(1 + |x| 2 + |x| 2 )|x -x| 2α ,
While all the other terms can be easily estimated using the results we have obtained already, for

E (tm,T ] |(f tm,x 3 (s-)-f tm,x 3 (s-))∂ 2 x Z n,tm,x s- |d[B n ] s 2 ≤ C(Ψ 12 (x)+Ψ 12 (x))(1+|x| 2 +|x| 2 )|x-x| 2α
we need the bound (59).

The result follows then from Gronwall's lemma.

|u n (t m , x) -u n (t m , x)| ≤ C(1 + Ψ(x) + Ψ(x))|x -x|, |D n m+1 u n (t m+1 , X n,tm,x tm+1 ) -D n m+1 u n (t m+1 , X n,tm,x tm+1 )| ≤ C(1 + Ψ 2 (x) + Ψ 2 (x))|x -x|, |u n x (t m , x) -u n x (t m , x)| ≤ C(1 + Ψ 2 (x) + Ψ 2 (x))|x -x|, |∂ x D n m+1 u n (t m+1 , X n,tm,x tm+1 ) -∂ x D n m+1 u n (t m+1 , X n,tm,x tm+1 )| ≤ C(1 + Ψ(x) + Ψ(x))|x -x| α , |∂ x D n m+1 u n (t m+1 , X n,tm,x tm+1 )| ≤ C(1 + Ψ 2 (x)), (60)
uniformly in m = 0, 1, . . . , n -1, where

Ψ(x) := 1 + |x| 6p0+8 . (61)
In addition, for

∂ x F n (t m+1 , x) := ∂ x f (t m+1 , x, u n (t m , x), D n m+1 u n (t m+1 , X n,tm,x tm+1
)) we have

|∂ x F n (t m+1 , x) -∂ x F n (t m+1 , x)| ≤ C(1 + Ψ(x) + Ψ(x))|x -x| α (62)
uniformly in m = 0, 1, . . . , n-1. The latter inequality follows from the assumption that the partial derivatives of f are bounded and Lipschitz continuous w.r.t. the spatial variables, from estimates proved in Proposition 4.2 and from those stated in (60) above.

From the calculations it can be seen that in general Assumption 2.3 can not be weakened if one needs ∂ x F n (t m+1 , x) to be locally α-Hölder continuous.

Technical results and estimates

In this section we collect some facts which are needed for the proofs of our results. We start with properties of the stopping times used to construct a random walk.

i) Eτ k = kh, (ii) E|τ 1 | p ≤ C(p)h p , (iii) E|B τ k -B t k | 2p ≤ C(p)E|τ k -t k | p ≤ C(p)(t k h) p 2 . (
The next lemma lists some estimates concerning the diffusion X defined by [START_REF] Kruse | BSDEs with monotone generator driven by Brownian and Poisson noises in a general filtration[END_REF] and its discretization [START_REF] Jańczak-Borkowska | Discrete approximations of generalized RBSDE with random terminal time[END_REF], where we assume that B and B are connected as in [START_REF] Henry-Labordere | A numerical algorithm for a class of BSDEs via the branching process[END_REF].

Lemma 5.2. Under Assumption 2.1 on b and σ it holds for p ≥ 2 that there exists a constant

C = C(b, σ, T, p) > 0 such that (i) E X s,y T -X t,x T p ≤ C(|y -x| p + |s -t| p 2 ), x, y ∈ R, s, t ∈ [0, T ], (ii) Ẽ sup τl ∧tm≤r≤τ l+1 ∧tm | Xt k ,x t k +r -Xt k ,x t k +τ l ∧tm | p ≤ Ch p 4 , 0 ≤ k ≤ n, 0 ≤ l ≤ n -k -1, 0 ≤ m ≤ n -k, (iii) E|∇X s,y T -∇X t,x T | p ≤ C(|y -x| p + |s -t| p 2 ), x, y ∈ R, s, t ∈ [0, T ], (iv) E sup 0≤l≤m ∇X n,t k ,x t k +t l p ≤ C, 0 ≤ k ≤ n, 0 ≤ m ≤ n -k, (v) Ẽ Xt k ,x t k +tm -X τ k ,y τ k +τm p ≤ C(|x -y| p + h p 4 ), 0 ≤ k ≤ n, 0 ≤ m ≤ n -k, (vi) Ẽ|∇ Xt k ,x t k +tm -∇ X τ k ,y τ k +τm | p ≤ C(|x -y| p + h p 4 ), 0 ≤ k ≤ n, 0 ≤ m ≤ n -k.
Proof. (i): This estimate is well-known.

(ii): For the stochastic integral we use the inequality of BDG and then, since b and σ are bounded, we get by Lemma 5.1 (ii) that Ẽ sup

τl ∧tm≤r≤τ l+1 ∧tm | Xt k ,x t k +r -Xt k ,x t k +τ l ∧tm | p ≤ C(p)( b p ∞ Ẽ|τ l+1 -τl | p + σ p ∞ E|τ l+1 -τl | p 2 ) ≤ C(b, σ, T, p) h p 2 .
(iii): This can be easily seen because the process (∇X s,y r ) r∈[s,T ] solves the linear SDE (12) with bounded coefficients.

(iv): The process solves (64). The estimate follows from the inequality of BDG and Gronwall's lemma.

(v): Recall that from ( 4) and ( 25) we have

X τ k ,y τ k +τm = Xn,t k ,y t k +tm = y + (0,tm] b(t k + r, Xn,t k ,y t k +r-)d[ Bn , Bn ] r + (0,tm] σ(t k + r, Xn,t k ,y t k +r-)d Bn r ,
and Xt k ,x t k +tm is given by Xt

k ,x t k +tm = x + tm 0 b(t k + r, Xt k ,x t k +r )dr + tm 0 σ(t k + r, Xt k ,y t k +r )d Br .
To compare the stochastic integrals of the previous two equations we use the relation

(0,tm] σ(t k + r, Xn,t k ,y t k +r-)d Bn r = ∞ 0 m-1 l=0 σ(t k+l+1 , Xn,t k ,y t k+l )1 (τ l ,τ l+1 ] (r)d Br .
We define an 'increasing' map i(r) := t l+1 for r in (t l , t l+1 ] and a 'decreasing' map d(r) := t l for (t l , t l+1 ] and split the differences as follows (using Assumption 2.1-(iii) for the coefficient b)

Ẽ Xt k ,x t k +tm -Xn,t k ,y t k +tm p ≤ C(b, p) |x -y| p + Ẽ tm 0 |r -i(r)| p 2 + | Xt k ,x t k +r -Xt k ,x t k +d(r) | p + | Xt k ,x t k +d(r) -Xn,t k ,y t k +d(r) | p dr +C(p) Ẽ| tm tm∧τm σ(t k + r, Xt k ,x t k +r )d Br | p +C(p) Ẽ| τm tm∧τm m-1 l=0 σ(t k+l+1 , Xn,t k ,y t k+l )1 (τ l ,τ l+1 ] (r)d Br | p +C(p) Ẽ| tm∧τm 0 σ(t k + r, Xt k ,x t k +r ) - m-1 l=0 σ(t k+l+1 , Xn,t k ,y t k+l )1 (τ l ,τ l+1 ] (r)d Br | p . (63)
We estimate the terms on the r.h.s as follows: by standard estimates for SDEs with bounded coefficients one has that

Ẽ tm 0 |r -i(r)| p 2 + | Xt k ,x t k +r -Xt k ,x t k +d(r) | p dr ≤ C(b, σ, T, p)h p 2 .
By the BDG inequality, the fact that σ is bounded and Lemma 5.

≤ C(σ, p) σ p ∞ Ẽ|τ m -t m | p 2 ≤ C(σ, p)(t m h) p 4 .
Finally, by the BDG inequality

Ẽ tm∧τm 0 σ(t k + r, Xt k ,x t k +r ) - m-1 l=0 σ(t k+l+1 , Xn,t k ,y t k+l )1 (τ l ,τ l+1 ] (r)d Br p ≤ C(p) Ẽ tm 0 m-1 l=0 |σ(t k + r, Xt k ,x t k +r ) -σ(t k+l+1 , Xn,t k ,y t k+l )| 2 1 (τ l ,τ l+1 ] (r)dr p 2 ≤ C(σ, p) Ẽ m-1 l=0 τl+1 ∧tm τl ∧tm |τ l+1 -t l+1 | p 2 + |τ l -t l+1 | p 2 + | Xt k ,x t k +r -Xt k ,x t k +τ l ∧tm | p +| Xt k ,x t k +τ l ∧tm -Xn,t k ,y t k+l | p dr ≤ C(σ, T, p) h p 2 + max 1≤l<m ( Ẽ|τ l -t l | p ) 1 2 + max 0≤l<m ( Ẽ sup τl ∧tm≤r≤τ l+1 ∧tm | Xt k ,x t k +r -Xt k ,x t k +τ l ∧tm | 2p ) 1 2 + Ẽ m-1 l=0 | Xt k ,x t k +τ l ∧tm -Xn,t k ,y t k+l | p (τ l+1 -τl ) .
Moreover, since τl+1τl is independent from | Xt k ,x t k +τ l ∧tm -Xn,t k ,y t k +t l | p we get by Lemma 5.1-(i)

Ẽ m-1 l=0 | Xt k ,x t k +τ l ∧tm -Xn,t k ,y t k+l | p (τ l+1 -τl ) = Ẽ m-1 l=0 | Xt k ,x t k +τ l ∧tm -Xn,t k ,y t k+l | p (t l+1 -t l ) ≤ C(T, p) Ẽ tm 0 | Xt k ,x t k +d(r) -Xn,t k ,y t k +d(r) | p dr + max 0≤l<m Ẽ| Xt k ,x t k +τ l ∧tm -Xt k ,x t k +t l | p .
Using Lemma

and

∇ Xt k ,x t k +tm = 1 + tm 0 b x (t k + r, Xt k ,x t k +r )∇ Xt k ,x t k +r dr + tm 0 σ x (t k + r, Xt k ,x t k +r )∇ Xt k ,x t k +r d Br . (65)
We may proceed similarly as in (v) but this time the coefficients are not bounded but have linear growth. Here one uses that the integrands are bounded in any L p (P).

Finally, we estimate the difference between the continuous-time Malliavin weight and its discrete-time counterpart.

Lemma 5.3. Let B and B be connected via [START_REF] Henry-Labordere | A numerical algorithm for a class of BSDEs via the branching process[END_REF]. Under Assumption 2.1 it holds that

Ẽ| Ñ t k tm σ(t k , X t k ) -Ñ n,τ k τm σ(t k+1 , X τ k )| 2 ≤ C(b, σ, T, δ) |X t k -X τ k | 2 + h 1 2 (t m -t k ) 3 2
, m = k + 1, ..., n.

Proof. For N n,τ k τm and N t k tm given by ( 11) and [START_REF] Crisan | On the Monte-Carlo simulation of BSDEs: An improvement on the Malliavin weights[END_REF], respectively, we introduce the notation Ñ t k tm σ(t k , X t k ) =: ≤ C(b, σ, T, δ)h.

For the third term Lemma 5.2-(vi) implies that

Ẽ| Kt k t k +t ℓ-1 (∇ Xt k ,Xt k t k +t ℓ-1 -∇ X τ k ,Xτ k τ k +τ ℓ-1 )| 4 ≤ C(b, σ, T ) σ 4 ∞ δ -4 (|X t k -X τ k | 4 + h).
The last term we estimate similarly to the second one, Ẽ|∇ X τ k ,Xτ k τ k +τ ℓ-1 ( Kt k t k +t ℓ-1 -Kn,τ k τ k +τ ℓ-1 )| ≤ C(b, σ, T, δ)(|X t k -X τ k | 4 + h).

To see (67) use the estimates (68).

We close this section with estimates concerning the effect of T m,± and the discretized Malliavin Proof. (i) By definition, T m,± X n t l = X n t l for l ≤ m -1, and for l ≥ m we have T m,± X n t l = X n tm-1 + b(t m , X n tm-1 )h ± σ(t m , X n tm-1 ) √ h +h l j=m+1 b(t j , T m,± X n tj-1 ) + √ h l j=m+1 σ(t j , T m,± X n tj-1 )ε j .

By the properties of b and σ and thanks to the inequality of Burkholder-Davis-Gundy and Hölder's inequality we see that σ (k+1,l)

E|X n t l -T m,
x D n k+1 X n t l-1 σ(t k+1 , X n t k ) p .

Since by Lemma 5.4 (i) we conclude that E|b (k+1,l)

x b x (t l , X n t l-1 )| 2p + E|σ (k+1,l)

x σ x (t l , X ≤ C(b, σ, T, p), the assertion follows by Gronwall's lemma.

(iii) This is an immediate consequence of (i).

α 4

 4

Definition 2 . 1 .

 21 (Definition of T m,+ , T m,-and D n m .) For any function F : {-1, 1} n → R, the mappings T m,+ and T m,-are defined by

Proposition 2 . 1 .

 21 If Assumption 2.3 holds, then

Lemma 4 . 1 .

 41 and recall the Malliavin weight and its properties from [20, Subsection 1.1 and Remark 3]. Let H : R → R be a polynomially bounded Borel function. If Assumption 2.1 holds and X t,x is given by (35) then setting

Theorem 4 . 1 .

 41 Let Assumption 2.1 and 2.2 hold. Then for any p ∈ [2, ∞) the following assertions are true.

  ≤ t ≤ s ≤ T,

T-

  Xt,x T and ∇ Xs,Xs T -∇ Xt,x T like in Lemma 5.2. For the Γ differences we first apply the inequalities of Hölder and BDG: Ẽ| Γs,Xs T

  y ( Θs,Xs r ) Γs,Xs r f y ( Θt,x r ) Γt,x r | q dr + Ẽ T s |f z ( Θs,Xs r ) Γs,Xs r f z ( Θt,x r ) Γt,x r | 2 dr q 2

  |f x ( Θs,Xs r )f x ( Θt,x r )| = |f x (r, Xs,Xs r , u(r, Xs,Xs r ), σ(r, Xs,Xs r )u x (r, Xs,Xs r

r)

  f y ( Θt,x r )| and |f z ( Θs,Xs r )f z ( Θt,x r )|. Applying these inequalities and Gronwall's lemma, we arrive at Ẽ[ Γs,Xs T -Γt,x T ] p ≤ C(c 2,3 4.2 , b, σ, f, g, T, p 0 , p)Ψ(x)|s -t| 1 2

Remark 4 . 1 .

 41 Under Assumption 2.3 we conclude that by Proposition 4.2 there exists a constant C = C(b, σ, f, g, T, p, p 0 ) > 0 such that

Lemma 5 . 1 .

 51 (Proposition 11.1[START_REF] Walsh | The rate of convergence of the binomial tree scheme[END_REF], Lemma A.1[START_REF] Geiss | Random walk approximation of BSDEs with Hölder continuous terminal condition[END_REF].) For all 0 ≤ k ≤ m ≤ n and p > 0, it holds for h = T n and τ k defined in (23) that

Lemma 5 . 4 . 2 , 1 2 ,

 54212 derivative D n k (see Definition 2.1) on X n . Under Assumption 2.1, and for p ≥ 2, we have(i) E|X n t l -T m,± X n t l | p ≤ C(b, σ, T, p)h p ≤ l, m ≤ n, 0 ≤ k < m ≤ n. (iii) E|D n k X n tm | p ≤ C(b, σ, T, p), 0 ≤ k ≤ m ≤ n.

  and [21, Theorem 5.4].

	Theorem 4.2. Consider the FBSDE (1) and let Assumptions 2.1 and 2.2 hold. Then for the
	solution u of the associated PDE

  depends on L f , C g , T, p 0 , κ 2 = κ 2 (b, σ, T, δ), C y 4.1 , C z 4.1 and on the bounds and Lipschitz constants of b and σ, and hence c 3 4.2 = c 3 4.2 (L f , K f , C g , b, σ, T, p 0 , δ).

	1-α 2 ,
	where c 3 4.2

Using Assumption 2.3 we are now in the position to improve the bound on Z s -Z t Lp(Pt,x)

given in Theorem 4.1. Proposition 4.1. If Assumption 2.3 holds, then there exists a constant C 4.1 > 0 such that for

  E| ξn,tm,xξn,tm,x| 2 ≤ C(Ψ 2 (x) + Ψ 2 (x))(1 + |x| 2 + |x| 2 )|x -x| 2α ,where we use |x -x| 2 ≤ C(1 + |x| 2 + |x| 2 )|x -x| 2α .The term |x -x| 2 appears for example in the

	uniformly for each t m ≤ t k < T . Inequality (57) then follows by applying the Cauchy-Schwarz inequality and standard L p -estimates for the process X n .
	(58): This can be shown similarly as Lemma 4.2-(iii) considering the BSDE for the difference
	∂ x Y n,tm,x tm	-∂ x Y n,tm,x tm	instead of (46) itself.
	(59): This one gets repeating again the proof of Lemma 4.2-(iii) but now for the BSDE (54).
	By our assumptions we have
	estimate of (∂ x X n,tm,x T	) 2 -(∂ x X n,tm,x T	) 2 . To see that
	E
	(tm,T ]
				t k	tm,x	|

  5.1-(iii) one concludes similarly as in the proof of (ii) that Ẽ| Xt k ,x t k +τ l ∧tm -Xt k ,x t k +t l | p ≤ C(b, σ, T, p)h

	p 4 . Then (63) combined with the above estimates implies that
	Ẽ Xt k ,x t k +tm -Xn,t k ,y t k +tm
			p 4 ).
	(vi): We have
	∇ Xn,t k ,y t k +tm	= 1 +	(0,tm]

p ≤ C(b, σ, T, p) |x -y| p + h

p 4 + Ẽ tm 0 | Xt k ,x t k +d(r) -Xn,t k ,y t k +d(r) | p dr . Then Gronwall's lemma yields Ẽ Xt k ,x t k +tm -Xn,t k ,y t k +tm p ≤ C(b, σ, T, p)(|x -y| p + h b x (t k + r, X

n,t k ,y t k +r-)∇ Xn,t k ,y t k +r-d[ Bn , Bn ] r + (0,tm] σ x (t k + r, Xn,t k ,y t k +r-)∇ Xn,t k ,y t k +r-d Bn r

  Bs and Ñ n,τ k τm σ(t k+1 , X τ k ) =: k+1 , X τ k ) σ(t k+ℓ , X τ k ,Xτ k τ k +τ ℓ-1 )1 s∈(τ ℓ-1 ,τ ℓ ] .By the inequality of BDG,(t mt k ) 2 Ẽ| Ñ t k tm σ(t k , X t k ) -Ñ n,τ k τm σ(t k+1 , X τ k )| 2 (a t k +sa n τ k +s ) 2 ds + Ẽ +s ) 2 1 (t m-k ,τ m-k ] (s)dsThe assertion follows then from Lemma 5.1 and from the estimatesẼ sup s∈[0,t m-k ]∩[τ ℓ-1 ,τ ℓ ] |a t k +sa n τ k +τ ℓ | 4 ≤ C(b, σ, T, δ)(|X t k -X n t k | 4 + h) Xt k ,Xt k t k +s ) and Kn,τ k τ k +τ ℓ-1 := σ(t k+1 , X τ k ) σ(t k+ℓ , X τ k ,Xτ k τ k +τ ℓ-1 )and notice that by Assumption 2.1 both expressions are bounded by σ ∞ δ -1 . To show (66) let us split a t k +sa n τ k +τ ℓ in the following way:a t k +sa n τ k +τ ℓ = Kt k t k +s (∇ Xt k ,Xt k t k +s -∇ Xt k ,Xt k t k +t ℓ-1 ) + ∇ Xt k ,Xt k t k +t ℓ-1 ( Kt k t k +s -Kt k t k +t ℓ-1 ) + Kt k t k +t ℓ-1 (∇ Xt k ,Xt k t k +t ℓ-1 -∇ X τ k ,Xτ k τ k +τ ℓ-1 ) + ∇ X τ k ,Xτ k τ k +τ ℓ-1 ( Kt k t k +t ℓ-1 -Kn,τ k τ k +τ ℓ-1 ). Xt k ,Xt k t k +t ℓ-1 | 4 ≤ C(b, σ, T, δ)h since one can show similarly to Lemma 5.2-(ii) that Ẽ sup s∈[τ ℓ-1 ∧t m-k ,τ ℓ ∧t m-k ] |∇ Xt k ,Xt k t k +s -∇ Xt k ,Xt k t k +t ℓ-1 | 4 ≤ C(b, σ, T, δ)h. |∇ Xt k ,Xt k t k +s | p ≤ C(b, σ, T, p) and Ẽ max 0≤ℓ≤m-k |∇ X τ k ,Xτ k τℓ +τ k | p ≤ C(b, σ, T, p). [τ ℓ-1 ∧t m-k ,τ ℓ ∧t m-k ] |∇ Xt k ,Xt k t k +t ℓ-1 ( Kt k t k +s -Kt k t k +t ℓ-1 )| 4 ≤ C(σ, δ)( Ẽ|∇ Xt k ,Xt k t k +t ℓ-1 | 8 ) [τ ℓ-1 ∧t m-k ,τ ℓ ∧t m-k ] (|t ℓ -s| 4 + | Xt k ,Xt k t k +s -Xt k ,Xt k t k +t ℓ | 8 )

	with
	a t k +s := ∇ Notice that ∇ Xt k ,Xt k t k +s Xt k ,Xt k σ(t k , X t k ) σ(t k +s, Xt k ,Xt k t k +s ) t and ∇ X τ k ,Xτ k and a n τ k +s := τm solve the linear SDEs (65) and (64), respectively. There-m-k ℓ=1 ∇ X τ k ,Xτ k τ k +τ ℓ-1 fore, Ẽ sup (68) σ(t = Ẽ t m-k 0 a t k +s d Bs -τm-k 0 a n 2 s∈[0,t m-k ] τ k +s d Bs For the second term we get
	Ẽ	= Ẽ sup	0	t m-k ∧τ m-k		0	∞	a 2 t k +s 1 (τ m-k ,t m-k ] (s)ds
		+ Ẽ m-k ℓ=1 τ k ≤ ∞ 0 (a n Ẽ	sup 1 2 ( Ẽ	sup	1 2	1 2
								1
								2
		+ Ẽ sup		1≤ℓ≤m-k	|a n τ k +τ ℓ | 4	1 2 .
								(66)
		Ẽ sup s∈[0,t m-k ]	|a t k +s | 4 + Ẽ max 1≤ℓ≤m-k	|a n τ k +τ ℓ | 4 ≤ 2 σ 4 ∞ δ -4 .	(67)
	So it remains to show these inequalities. We put
	Kt k t Then
	Ẽ	sup
		1 t m-k	t m-k		1 t m-k	0	τm-k	a n τ k +s d Bs

0 a t k +s d s∈[0,t m-k ]∩(τ ℓ-1 ,τ ℓ ] a t k +sa n τ k +τ ℓ 4 1 2 ( Ẽ|τ ℓτℓ-1 | 2 ) s∈[0,t m-k ] |a t k +s | 4 + Ẽ max ( Ẽ|t m-kτm-k | 2 ) k +s := σ(t k , X t k ) σ(t k + s, s∈[τ ℓ-1 ∧t m-k ,τ ℓ ∧t m-k ] | Kt k t k +s (∇ Xt k ,Xt k t k +s -∇ Xt k ,Xt k t k +t ℓ-1 )| 4 ≤ σ 4 ∞ δ -4 Ẽ sup s∈[τ ℓ-1 ∧t m-k ,τ ℓ ∧t m-k ] |∇ Xt k ,Xt k t k +s -∇ s∈s∈

  Ẽ|∇ X τ k ,Xτ k τ k +τ ℓ-1 | 8 ) 1 2 (|X t k -X τ k | 8 + Ẽ|X τ k ,Xτ k τ k +τ ℓ-1 -Xt k ,Xt k t k +t ℓ-1 | 8 )

	1
	2

4

≤ C(σ, δ)(

  ± X n t l | p ≤ C(p) E σ(t m , X n tm-1 ) √ h(1 ± ε m ) p + h p E -T m,± X n tj-1 | p .It remains to apply Gronwall's lemma.(ii) By the inequality of Burkholder-Davis-Gundy (BDG) and Hölder's inequality,

						l j=m+1	b(t j , X n tj-1 ) -b(t j , T m,± X n tj-1 )	p
	+ h	p 2 E	l j=m+1	σ(t j , X n tj-1 ) -σ(t j , T m,± X n tj-1 )	2	p 2
	≤ C(p) σ p ∞ h tj-1 E ∇X p 2 + h( b x p ∞ t p-1 l-m + σ x p ∞ t p l 2 -1 l-m ) j=m+1 E|X n n,t k ,X n t k tm -k+1 X n tm D n σ(t k+1 , X n t k )
							n,t k ,X n t k t l-1	-b (k+1,l) x	k+1 X n t l-1 D n σ(t k+1 , X n t k )
				p 2	m	E σ x (t l , X n t l-1 )∇X	n,t k ,X n t k t l-1
				l=k+2

p ≤ C(p, T ) |b x (t k+1 , X n t k )h + σ x (t k+1 , X n t k ) √ hε k+1 | p + h p m l=k+2 E b x (t l , X n t l-1 )∇X p + h

  n t l-1 )| 2p ≤ C(b, σ, T, p)h p ,

	and Lemma 5.2 implies that
	E sup k+1≤l≤m	∇X	n,t k ,X n t l-1 t k	2p

Acknowledgements

Christel Geiss would like to thank the Erwin Schrödinger Institute, Vienna, for hospitality and support, where a part of this work was written.