A note on strong approximation of SDEs with smooth coefficients that have at most linearly growing derivatives
Thomas Müller-Gronbach Larisa Yaroslavtseva
math.PR

Approximation of SDEs with smooth coeffients with derivatives of linear growth ]A note on strong approximation of SDEs with smooth coefficients that have at most linearly growing derivatives


Müller-Gronbach and Yaroslavtseva]
Thomas Müller-Gronbach and Larisa Yaroslavtseva

Fakultät für Informatik und Mathematik

Universität Passau

Innstrasse 33 

94032 Passau

Germany larisa.yaroslavtseva@uni-passau.de, thomas.mueller-gronbach@uni-passau.de



Recently, it has been shown in [Jentzen, A., Müller-Gronbach, T., and Yaroslavtseva, L., Commun. Math. Sci., 14, 2016] that there exists a system of autonomous
 stochastic differential equations (SDE) on the time interval [0,T] with infinitely  differentiable and bounded coefficients  such that no strong approximation method 
based on evaluation of the
driving Brownian motion at finitely many fixed times 
   in [0,T], e.g. on an equidistant grid, 
    can converge in absolute mean to the solution at the final time with a polynomial rate in terms of the number of Brownian motion values that are used.
In the literature on strong approximation of SDEs, polynomial error rate results are typically
 achieved under the assumption that the first order derivatives of the coefficients of the equation satisfy a polynomial growth condition. This assumption is violated for the 
    pathological  SDEs from  the above mentioned negative result.
    However, in the present
 article we  construct an SDE with smooth coefficients that have first order derivatives of at most linear growth such  that  the solution at the final time can not be approximated with a polynomial rate, whatever method based on observations of the
driving Brownian motion at finitely many fixed times is used. 
Most interestingly, it turns out that using a method that adjusts the number of evaluations of the driving Brownian motion to its actual path, the latter SDE can be approximated  with rate 1 in terms of the average number of evaluations that are used. To the best of our knowledge, this is only the second example in the literature of an SDE for which there exist adaptive methods that perform superior 
to non-adaptive ones with respect to the convergence rate. 




[
    [
    December 30, 2023
=====================











§ INTRODUCTION


Let d,m∈, T∈(0, ∞), consider a d-dimensional system of autonomous stochastic differential equations (SDE)

    dX(t)     = μ(X(t))   dt + σ(X(t))   dW(t),    t∈ [0,T],
    
    X(0)     = x_0

with a deterministic initial value x_0∈^d, a drift coefficient μ^d→^d, a diffusion coefficient σ^d→^d× m and an m-dimensional driving Brownian motion W, and assume that (<ref>) has a unique strong solution (X(t))_t∈[0, T]. 
A fundamental problem in the numerical analysis of SDEs is to characterize when 
the solution at the final time X(T) can be approximated  with a polynomial 
error rate based on  finitely many evaluations of the driving Brownian motion W 
in terms of explicit regularity conditions on the coefficients μ and σ.


It is well-known that if the coefficients μ and σ are globally Lipschitz continuous then the classical Euler-Maruyama scheme achieves the rate of convergence 1/2, see <cit.>. Moreover,
the recent literature on numerical approximation of SDEs contains a number
of results on approximation schemes that are specifically designed for 
     SDEs with
non-Lipschitz coefficients and achieve
polynomial convergence rates 
under weaker conditions on μ and σ, 
see e.g.
<cit.>
for SDEs with globally monotone coefficients
and e.g.
<cit.> 
for SDEs with possibly non-monotone coefficients.

On the other hand, it has recently been shown in <cit.>  that for any sequence  (a_n)_n∈⊂ (0,∞), which may converge to zero arbitrarily slowly,  there exists an SDE (<ref>) with d=4 and m=1 and with infinitely  differentiable and bounded coefficients μ and σ such that no sequence of approximations X_n(T) of X(T), where X_n(T) is
based on n evaluations of the driving Brownian
motion W at fixed time points in [0,T], can converge to X(T) in absolute mean  faster than the given sequence (a_n)_n∈. 
More formally, for this SDE one has for every n∈,

    inf_
          s_1,…,s_n∈ [0,T]
        
    
         u^n→^4  measurable[
        |
          X( T )
          -
          u( W( s_1 ), …, W( s_n )
          )
        |]
    ≥  a_n.

In <cit.> it has been proven 
that the negative result (<ref>) can even be achieved  with m=1 and d=2 in place of d=4. 
In particular, (<ref>) implies that there exists an SDE (<ref>) with infinitely  differentiable and bounded coefficients μ and σ such that
its solution at the final time can not be approximated with a polynomial mean error rate  based on 
evaluations of the driving Brownian
motion W at finitely many fixed time points in [0,T], i.e., for every α>0,

    lim_n→∞( n^α·inf_
          s_1,…,s_n∈ [0,T]
        
    
         u^nm→^d  measurable[|X(T)-u(W(s_1), …,
    W(s_n))|]) =∞.

 We add that the latter statement for the special case when the approximation u(W(s_1), …,
W(s_n)) is given by the Euler-Maruyama scheme with 
time step 1/n
has first been shown in <cit.>.  

The proof of the negative result (<ref>) in <cit.> is constructive. Each of the respective SDEs  is given by X(0)=0 and  

    dX_1(t)     = dt,   dX_2(t)  = f(X_1(t)) dW(t),  
    dX_3(t)  = g(X_1(t)) dW(t),
    
    dX_4(t)     = h(X_1(t)) ·cos(X_2(t)·ψ(X_3(t))) dt

for t∈ [0,T], where f,g,h→ are infinitely  differentiable, bounded, nonzero and satisfy {f ≠ 0}⊂ (-∞, τ_1], 
{g ≠ 0}⊂ [τ_1, τ_2], {h≠ 0}⊂ [τ_2, T], ∫_τ_2^T h(t)  dt ≠ 0 and inf_x∈ [0,τ_1/2] |f'(x)| >0 for some 0<τ_1<τ_2<T, and ψ→ (0,∞) is infinitely differentiable, strictly increasing and satisfies lim_x→∞ψ(x) = ∞. Under these assumptions 
the fourth component of the solution of the SDE (<ref>) at the final time is given by 

    X_4(T)= cos(∫_0^τ_1f(t) dW(t)·ψ(∫_τ_1^τ_2g(t) dW(t)))·∫_τ_2^T h(t)   dt

and there exist c_1,c_2,c_3∈ (0,∞) such that for every n∈,

    inf_
          s_1,…,s_n∈ [0,T]
        
    
         u^n→ measurable[
        |
          X_4( T )
          -
          u( W( s_1 ), …, W( s_n )
          )
        |]
    ≥  c_1·exp(-c_2· (ψ^-1(c_3 · n^3/2)^2),

see Corollary 4.1 in <cit.>.


   It follows from (<ref>) that
if 

    ∀ q∈ (0,∞)  lim_x→∞exp(-q x^2)·ψ (x) = ∞

then a polynomial  rate of convergence to zero of the left hand side in (<ref>) can not be achieved, see Corollary 4.2 in <cit.>.
On the other hand it is straightforward to check that the equidistant Euler-Maruyama scheme for the SDE (<ref>)
 achieves a polynomial mean error rate if the derivative  ψ' of ψ is of at most polynomial growth.
The latter two facts are reflected in the growth properties of the first order
 derivatives of the coefficients μ and σ of the SDE (<ref>). 
 All of
the first order 
  derivatives of μ and σ are globally bounded, up to the  derivatives 

    ∂μ_4/∂ x_2(x) =  -h(x_1)·ψ(x_3)·sin(x_2·ψ(x_3)),  ∂μ_4/∂ x_3(x) =  -h(x_1)· x_2·ψ'(x_3)·sin(x_2·ψ(x_3)),
 
which are both of at most polynomial growth if and only if ψ'  is of at most  polynomial growth.


For the vast majority of SDEs with locally Lipschitz continuous coefficients used for modelling in applications it holds that the first order  derivatives of the coefficients are of at most polynomial growth.
Moreover, a polynomial growth condition on the 
first order 
derivatives of the coefficients of an SDE is 
one of the standing assumptions
in the literature
 when polynomial mean error rates are obtained under 
monotonicity 
 conditions, see e.g.
 <cit.>. 
         Therefore it is 
important to investigate whether a sub-polynomial rate of convergence as in (<ref>) may also happen  when the first order 
 derivatives of the coefficients are of at most polynomial growth.

This question can easily be answered with a yes. For the choice ψ(x) = exp(x^3), which satisfies (<ref>), the random variable X_4(T) in (<ref>) can also be obtained as the fifth component of the solution at the final time of an SDE given by Y(0)=(0,0,0,1,0)
 and

    dY_1(t)   =dt,   dY_2(t) =f(Y_1(t))  dW(t),   dY_3(t) =g(Y_1(t))  dW(t),
    
    dY_4(t)   =u(Y_1(t)) · Y_3^3 (t)· Y_4(t) dt,    
    dY_5(t)=v(Y_1(t)) ·cos(Y_2(t)· Y_4(t))  dt

for t∈ [0,T],
where f, g, h satisfy the conditions stated below the SDE (<ref>) and, additionally, f' is bounded,  
and u,v→ are infinitely differentiable and satisfy  
{u≠ 0}⊂ [τ_2, τ_3],  {v≠ 0}⊂
[τ_3, T], ∫_τ_2^τ_3 u(s)  ds=1 and 
∫_τ_3^T v(s)  ds=∫_τ_2^T h(t) dt for some τ_3∈ (τ_2,T). Clearly, the coefficients of the SDE (<ref>) have first order derivatives of at most polynomial growth and Y_5(T) = X_4(T).



Note, however, that in contrast to the solution X of the SDE (<ref>), the solution Y of the SDE (<ref>) is not integrable at any time 
t∈[τ_3, T].
In fact, it is easy to see that

    [sup_t∈[0, T]|X(t)|] < ∞,  inf_t∈[τ_3, T][|Y_4(t)|] = ∞.

It therefore seems reasonable to modify the question posed above and 
to
ask whether 
a sub-polynomial rate of convergence as in (<ref>) may also happen
for an SDE (<ref>)
 that has smooth coefficients with first order  derivatives of at most polynomial growth and a  solution X with  

    [sup_t∈[0, T]|X(t)|] < ∞.
 
 
In the actual paper we show that the answer to this question is positive as well. More precisely,
consider the 7-dimensional SDE given by X(0)=(0,0,0,0,1,0,0) and 

    dX_1(t)   =dt,   dX_2(t) =f(X_1(t))  dW(t),
    
     dX_3(t)      =f^2(X_1(t)) dt + 2 X_2(t)· f(X_1(t))  dW(t),
    
    dX_4(t)   = 14 g'(X_1(t))· X_3(t)  dt,   
    dX_5(t) =X_4(t)· X_5(t)  dt,
    
    dX_6(t)     = h'(X_1(t))· X_5(t)(1+X_2^2(t))^1/2·ln^2(2 + X_2^2(t) ),   dX_7(t) = X_5(t)· X_6(t)  dt

for t∈ [0,T], where f,g,h→ satisfy the conditions stated below the SDE (<ref>) and, additionally,
 g,h≥ 0,
f' is bounded
  and   ∫_0^τ_1 f^2(t)  dt = ∫_τ_1^τ_2 g(t)  dt = ∫_τ_2^T h(t)  dt =1.
  See Example <ref> for a possible choice of f,g,h. 
 The assumptions on the functions f,g and h imply that 
 all of the first order  derivatives of 
 the coefficients of the SDE (<ref>) are of at most linear growth and the solution X of the SDE (<ref>) satisfies the moment condition (<ref>), see Lemmas <ref> and <ref>. Moreover, as a consequence of
Theorem <ref> we obtain
that there exists c∈ (0,∞) such that for all n∈,

    inf_
          s_1,…,s_n∈ [0,T]
        
    
         u^n→^7  measurable[|
          X( T )
          -
          u( W( s_1 ), …, W( s_n )
          )
        |]
    ≥  c·1/ln^2(n+1),

and therefore X(T) can not be approximated with a polynomial mean error rate  based on 
evaluations of the driving Brownian
motion W at finitely many fixed time points in [0,T]. To the best of our knowledge this is the first result in the literature, which shows that a sub-polynomial rate of convergence may happen even then when the first order derivatives of the coefficients are of at most polynomial growth.   It  implies in particular that for such SDEs 
      even 
 tamed or projected versions of the Euler-Maruyama scheme or the Milstein scheme, which are specifically designed to         cope with the case of 
superlinearly growing coefficients, see e.g. <cit.>
 may fail to achieve a polynomial convergence rate.

The negative result (<ref>)
covers only approximations that are based on n evaluations of the driving Brownian motion W at fixed time points s_1,…,s_n∈[0,T] and leaves it open whether a polynomial mean error rate can  be achieved by employing approximations that may 
    adapt 
the number as well as the location of the evaluation sites of
W 
to the actual path of W, e.g. by  numerical schemes that adjust the actual step size according to a
criterion that is based on the values of  W observed so far, see e.g.
<cit.> and the references therein for methods of this type. However, it is
well-known that for a huge class of SDEs (<ref>) with  globally Lipschitz continuous coefficients μ and σ  adaptive approximations of the latter type  can not achieve a better  rate of convergence compared to what is
best possible for non-adaptive ones, which at the same time coincides with the best possible rate of convergence that can be achieved by approximations based on evaluating  W at n equidistant times,
see <cit.> and the discussion on asymptotic constants therein. Moreover, it has recently been shown in <cit.> that the SDE (<ref>) with ψ satisfying (<ref>) 
can not be approximated with
a polynomial mean error rate even then when adaptive approximations may be used.

Up to now there seems to be only 
one
example of an SDE known in the literature, 
   for which
adaptive approximations are superior to non-adaptive ones with respect to the convergence rate. 
In <cit.> it has been shown that for the one-dimensional squared
Bessel process, i.e. the solution of the SDE (<ref>) with d = m =1, μ=1 and σ(x)=2√(|x|), any non-adaptive approximation
 of X(T) based on n equidistant evaluations of W can
  only achieve a mean error rate of order 1/2 in terms of n, while for every α∈ (0,∞) there exist c∈ (0,∞) and a sequence of approximations X_n(T), each based on n sequentially chosen evaluations of W, such that [|X(T)- X_n(T)|] ≤ c· n^-α. 

Interestingly it turns out that the SDE (<ref>) provides the second 
example    after <cit.>  
of an SDE in the literature, for which  there exist adaptive approximations 
      that perform superior to non-adaptive ones with respect to the convergence rate.     
Indeed,  there exists c∈ (0,∞) and  a sequence of approximations X_n(T), each based on n sequentially chosen evaluations of W on average, such that for all n∈,

    [|X(T)- X_n(T)|] ≤ c· n^-1,

see Theorem (<ref>). 

We briefly describe the content of the paper. 
In Section <ref> we introduce the particular SDE with smooth coefficients that
is studied in the present
paper and we discuss moment properties of its solution.  
Our main results on a sub-polynomial lower error bound for non-adaptive methods  (Theorem <ref>) and a polynomial upper error bound for a suitable adaptive method (Theorem <ref>) are stated in Section <ref>. The respective proofs are   carried out in Sections <ref> and <ref>. Section <ref> is devoted to a discussion of our results and naturally arising open questions.








§ AN SDE WITH SMOOTH COEFFICIENTS THAT HAVE AT MOST LINEARLY GROWING DERIVATIVES




Throughout this article we fix the following setting. 


Let 
T  ∈ (0,∞),
let
( Ω, ℱ,  )
be a probability space with a normal filtration
( ℱ_t )_ t ∈ [0,T]
and let
W  [0,T] ×Ω→
be a
standard ( ℱ_t )_ t ∈ [0,T]-Brownian motion
on ( Ω, ℱ,  ).

Let  0<τ_1<τ_2<T and let f, h, g ∈ C^∞(, ) satisfy 

    {f≠ 0}⊆ ( - ∞, τ_1 ],  {g≠ 0}⊆ [ τ_1, τ_2 ],  {h≠ 0}⊆ [ τ_2, T]

 as well as 

    sup_t∈ ( - ∞, τ_1 ]| f(t)| <∞,  sup_t∈ ( - ∞, τ_1 ]| f'(t)| <∞,  inf_ t∈ [ 0, τ_1/2  ]  | f'(t) | > 0,   g≥ 0,   h≥ 0

  and

    ∫_0^τ_1 f^2(t)  dt=
    ∫_τ_1^τ_2 g(t)  dt=
     ∫_τ_2 ^ T  h(t)   dt =1.

See the following example for a possible choice of f,g and h.

 Define f, g, h→ by

    f(x)      = _(-∞,τ_1)(x)·exp(      
          
            1
          
            x - τ_1
          ),
    g(x)      = _(τ_1,τ_2)(x)·exp(      
           1 τ_1 - x  +  1  x - τ_2 ),
    h(x)      =
        _(τ_2,T)(x)·exp(      
           1 τ_2 - x  +  1  x - T ).

Then the functions 

    f   =(∫_0^τ_1(f(s))^2 ds)^-1/2·f ,    
    g= (∫_τ_1^τ_2g(s) ds)^-1·g,   h= (∫_τ_1^τ_2h(s) ds)^-1·h
 
satisfy f,g,h∈ C^∞(, ) as well as the conditions (<ref>)-(<ref>).




Let p∈ [1, ∞) and define
μ, σ^7 →^7
as well as x_0∈^7 by

    μ(x)     = ( 1, 0, f^2(x_1), g'( x_1 )4p· x_3, x_4· x_5,  h'( x_1 ) · x_5(1+x_2^2)^1/2p·ln^2/p (2+x_2^2),x_5· x_6 ),
    σ(x)    =   (    0, f( x_1 ) , 2x_2· f(x_1), 0, 0,0,0  ),
    
      x_0   =(0,0,0,0,1,0,0).


 We have μ,σ∈ C^∞(^7,^7). Moreover, there exists c∈ (0,∞) such that for all x∈^7,

    ∑_i,j=1^7 (  |∂μ_i∂ x_j(x)| +  |∂σ_i∂ x_j(x)|)≤ c· (1+|x|).



Infinite differentiability of μ and σ is an immediate consequence of the definition of these functions and the fact that f,g,h∈ C^∞(,). Moreover, it is straightforward to check that there exists c∈ (0,∞) such that for all i,j∈{1,…,7}  and x∈^7,

    |∂σ_i∂ x_j(x)| ≤ c·(|f(x_1)|+|f'(x_1)|)· (1+|x|)

and

    |∂μ_i∂ x_j(x)| ≤ c·(|f(x_1)|· |f'(x_1)| + |g'(x_1)| + |g”(x_1)| + |h'(x_1)| + |h”(x_1)| + 1)· (1+|x|),

which jointly with the fact that g,h∈ C^∞(,) and 
   the properties (<ref>) and (<ref>) 
yields at most linear growth for all first order derivatives of μ and σ.



We study the SDE (<ref>) with m=1, d=7 and x_0,μ,σ given by (<ref>), i.e. X(0)=(0,0,0,0,1,0,0)^⊤ and 

    dX_1(t)   =dt,   dX_2(t) =f(X_1(t))  dW(t),
    
     dX_3(t)      =f^2(X_1(t)) dt + 2 X_2(t)· f(X_1(t))  dW(t),
    
    dX_4(t)   = 14p g'(X_1(t))· X_3(t)  dt,   
    dX_5(t) =X_4(t)· X_5(t)  dt,
    
    dX_6(t)     = h'(X_1(t))· X_5(t)(1+X_2^2(t))^1/2p·ln^2/p(2 + X_2^2(t) ),   dX_7(t) = X_5(t)· X_6(t)  dt




Observing (<ref>) and using Itô's formula for the component X_3 it is straightforward to see that  the equation (<ref>) has a unique strong solution given by

    X_1(t)     = t ,
      
      X_2(t) = ∫_0^min( t, τ_1 )  f(s)   dW(s),   X_3(t) = X_2^2(t),
    
    
     X_4(t)     = 14p X_2^2(τ_1)· g(t),    X_5(t)  =  exp(14p 
      X_2^2(τ_1)·∫_0^min( t , τ_2 )  g(s)   ds ) ,
    
    
      X_6(t)     =
       X_5(τ_2)(1+X_2^2(τ_1))^1/2p·ln^2/p (2+X_2^2(τ_1))·
     h(t),
    
     X_7(t)     =      X_5^2(τ_2)(1+X_2^2(τ_1))^1/2p·ln^2/p (2+X_2^2(τ_1))·∫_0^t h(s)  ds

for all t ∈ [0,T]. In particular, by (<ref>),

    X_1(T)     = T ,    X_2(T) =  X_2(τ_1) =∫_0^τ_1   f(s)   dW(s),
         X_3(T) = X_2^2(T),
    
     X_4(T)    = 0,    X_5(T)  =  exp(14p 
      X_2^2(τ_1)),    X_6(T) = 0,
    
      X_7(T)      = exp(1/2p
      X_2^2(τ_1))(1+X_2^2(τ_1))^1/2p·ln^2/p (2+X_2^2(τ_1)).


Next we discuss integrability properties of the solution X.

We have X_2(τ_1)∼𝒩( 0,  1). Moreover, for all q∈(0, ∞),

    [sup_t∈[0,T] |X(t)|^q]<∞  ⇔   q≤ p.




The first statement follows immediately from the definition of X_2(τ_1) and the fact that [X_2^  2(τ_1)] = ∫_0^τ_1 f^2(t)  dt= 1, due to (<ref>). Moreover, applying the Burkholder-Davis-Gundy  inequality we obtain that for all q∈(0, ∞) there exists c∈(0, ∞) such that

    [sup_t∈[0,T] |X_2(t)|^q] ≤ c·(∫_0^T f^2(t)  dt)^q2 =c.


 Employing (<ref>), (<ref>) and the properties of g we conclude that for all q∈(0, ∞), 

    [sup_t∈[0,T] |X_4(t)|^q] = 1(4p)^q·[|X_2(τ_1)|^2q]·sup_t∈ [τ_1,τ_2] (g(t))^q < ∞.

Furthermore, (<ref>), (<ref>), (<ref>) and the fact that  X_2(τ_1)∼𝒩( 0,  1) imply that for all q ∈ (0,2p), 

    [sup_t∈[0,T] |X_5(t)|^q] = [exp(q4pX_2^2(τ_1))] = √(2p2p-q).

By (<ref>), the latter  equality and the properties of h we get that for all q ∈ (0,2p), 

    [sup_t∈[0,T] |X_6(t)|^q] ≤1ln^2q/p(2)·[|X_5(τ_2)|^q]·sup_t∈[τ_2,T] h^q(t) <∞.

Finally, by (<ref>) we see that for all q∈(0, ∞), 

    [sup_t∈[0,T] |X_7(t)|^q]     = [exp(q/2p
      X_2^2(τ_1))(1+X_2^2(τ_1))^q/2p·ln^2q/p (2+X_2^2(τ_1))]  = √(2π)∫_0^∞exp(q-p2p· x^2) (1+x^2)^q/2p·ln^2q/p(2+x^2)  dx,

and the latter quantity is finite if and only if q≤ p.







§ LOWER AND UPPER ERROR BOUNDS

 

We study strong approximation of the solution X of the equation (<ref>) at the final time T.
The following result shows that X_7(T) and thus X(T) as well 
can not be approximated in p-th mean sense
 with a polynomial error rate in terms of the number of evaluations of the driving Brownian motion W as long as the number and the location of the evaluation nodes for W are not chosen in a  path-dependent way.


  There exists c∈(0, ∞) such that for all n∈,

    inf_
          s_1,…,s_n∈ [0,T]
        
    
         u^n→ measurable([|
          X_7( T ) -u(W(s_1), …, W(s_n))
        |^p])^1p≥ c·1/ln^2/p(n+1).




Our next result shows that a polynomial p-th mean error rate 
for approximation of X(T)
 can be achieved if the number 
 of the evaluation nodes for W is adjusted to the current path of W. 


For n∈ we use  W_n  [ 0, τ_1 ] ×Ω→ to denote the piecewise linear interpolation of W on [0,τ_1] at the nodes t_i= i/n·τ_1, i=0,…,n, i.e.
 
    W_n( t ) =  t - t_i-1/τ_1/n ·
      W( t_i) +   t_i- t  /τ_1/n · W( t_i-1),   t∈[t_i-1,t_i],

for  i∈{1, …, n}. We define approximations of the single components of X(T) in the following way.  Put

    X_n, 1(T)    =T,   X_n, 2(T)=-∫_0^τ_1f'(t)·W_n(t) dt,  X_n, 3(T)= X_n, 2^2(T),
    X_n, 4(T)     = 0,  X_n, 5(T)=exp(14p X_n, 2^2),  X_n, 6(T)=0.

Next, let 

    a_ℓ=2√(lnℓ)

for  ℓ∈ and put

    X^*_n, 2(T)=∑_ℓ=1^∞X_ℓ n, 2(T)· 1_[a_ℓ, a_ℓ+1)(|X_n, 2(T)|).
  
Finally, define  G→ by 

    G(x)=exp(1/2p
      x^2)/(1+x^2)^1/2p·ln^2/p (2+x^2),   x∈,

and put

    X^∗_n, 7(T)=G(X^*_n, 2(T))

as well as

    X^∗_n(T)=(X_n, 1(T),…,X_n, 6(T), X^∗_n, 7(T) ).


Clearly, the random number of evaluations of W  used by the approximation  
X^∗_n(T) is given by

    cost(X^∗_n(T)) = n∑_ℓ=1^∞ℓ·_[a_ℓ, a_ℓ+1)(|X_n, 2(T)|).




  There exists c∈ (0,∞) such that for all n∈,

    [cost(X^∗_n(T))]≤ c· n   and  ([|
          X( T ) -X^∗_n(T)
        |^p])^1p≤c/n.



Finally, we show that for q<p a polynomial q-th mean error rate
for approximation of X(T)
 can be achieved with a sequence of non-adaptive approximations. For n∈ put 

    X_n,7(T) = G(X_n,2(T))

with G given by (<ref>) and define

    X_n(T)=(X_n, i(T))_i=1,…,7.

Note that X_n(T) = u_n(W(τ_1/n),W(2τ_1/n),…, W(τ_1)) for some function
u_n^n→^7.


  Let q∈[0,p). Then there exists c∈ (0,∞) such that for all n∈,

    ([|
          X( T ) -X_n(T)
        |^q])^1q≤c/n.






§ PROOF OF THEOREM <REF>

For the proof of Theorem <ref> we employ the following lemma, which is a straightforward generalization of Lemma 4.1 in  <cit.>. 

Let
(Ω_1, 𝒜_1)
and
(Ω_2, 𝒜_2)
be measurable spaces
and let
V_1 Ω→Ω_1
and
V_2, V_2', V_2” Ω→Ω_2
be random variables such that

    _ (V_1, V_2)  =
      _ (V_1, V_2')  =
      _ (V_1, V_2”)  
      .

Then
for all q∈[1, ∞)  and for all measurable mappings
ΦΩ_1×Ω_2→
and
φΩ_1→,


    ([
        |Φ(V_1,V_2)- φ(V_1)|^q
      ])^1/q≥ 1 / 2  ([
        | Φ( V_1, V_2' ) - Φ( V_1, V_2” ) |^q
      ])^1/q
      .






Observe that
(<ref>)
ensures that

    [
        | Φ(V_1, V_2) - φ(V_1) |^q
      ]
      =
      [
        |
          Φ( V_1, V_2' ) - φ(V_1)
        |^q
      ]
      =
      [
        | Φ(V_1,V_2”) - φ(V_1) |^q
      ]
      .

This and the  Minkowski's inequality imply that

    ([
        | Φ(V_1,V_2) - φ(V_1) |^q
      ])^1/q   = 1 / 2  (([
        | Φ(V_1,V_2') - φ(V_1) |^q
      ])^1/q+([
        | Φ(V_1,V_2”) - φ(V_1) |^q
      ])^1/q) 
       ≥ 1 / 2  ([
        | Φ(V_1,V_2') - Φ(V_1,V_2”) |^q
      ])^1/q
     ,

  which finishes the proof of the lemma.



We start with the proof of Theorem <ref>. 
Let n∈ and s_1, …, s_n∈ [0,T]. Clearly, there exist 0≤ t_0 < t_1 ≤ T such that

    [t_0,t_1]⊂ [0,τ_1/2],   (t_0,t_1)∩{s_1,…,s_n} = ∅,   t_1-t_0 = τ_12(n+1).

Define  processes
W, B  [ t_0, t_1 ] ×Ω→
and
W( [ 0, t_0 ] ∪ [ t_1, T ] ) ×Ω→
    by

    W( t ) =  (t - t_0) / ( t_1 - t_0 ) ·
      W( t_1 ) +  ( t_1 - t ) / ( t_1 - t_0 ) · W( t_0 )
      ,
          
      B( t )
      = W( t ) - W( t )

   for t ∈ [ t_0, t_1 ]   
and by
W( t ) = W( t )
for 
t ∈ [ 0, t_0 ] ∪ [ t_1, T ]. Moreover, let

    Y_1   =-∫_0^t_0 f'(s)· W(s)  ds-∫_t_0^t_1 f'(s)·W(s)  ds-∫_t_1^τ_1 f'(s)· W(s)  ds, 
    
    Y_2   =-∫_t_0^t_1 f'(s)· B(s)  ds.

By Itô's formula and (<ref>) we have -a.s. 

    Y_1+Y_2= ∫_0^τ_1 f(s)  dW(s).

 Hence, by (<ref>), -a.s.

    X_7(T) = G(Y_1+Y_2),

where G→ is given by (<ref>).

Let u^n→ be a  measurable mapping. Using (<ref>) we obtain 

    [|
           X_7( T )-u(W(s_1), …, W(s_n))
        |^p]=[|
          G(Y_1+Y_2) -u(W(s_1), …, W(s_n))
        |^p].

The first two statements in (<ref>) imply that  
there exist measurable functions
Φ_1, φ
  C(
    [ 0, t_0 ] ∪ [ t_1 , T ] , ) → and  Φ_2 
  C(
    [t_0, t_1] , ) →
such that 

    Y_1 =
      Φ_1(
        W
     ),    Y_2=Φ_2(B),    u(W(s_1), …, W(s_n))=φ(W).
 
Moreover, W and B are independent and B has a symmetric distribution, which yields

    _ ( W, B ) 
    
    =
      _ ( W, - B ) .

We may thus apply Lemma <ref> with Ω_1 = C( [0, t_0] ∪ [t_1 , T] ,  ),
Ω_2 = C( [t_0, t_1] ,  ), V_1=W, V_2=V_2'=B, V_2”=-B, Φ(w̃,b)=G(Φ_1(w̃)+Φ_2(b)) for (w̃,b)∈Ω_1×Ω_2 and φ as above, and observing the fact that Φ_2(-B)=-Φ_2(B) we conclude that 

    [|
          G(Y_1+Y_2) -u(W(s_1), …, W(s_n))
        |^p]≥12^p [|
          G(Y_1+Y_2) -G(Y_1-Y_2)
        |^p].


For the analysis of the right hand side in (<ref>) we first collect useful properties of the random variables Y_1 and Y_2 and the function G.  

Clearly, Y_1 and Y_2 are centered normal Gaussian variables. Moreover,  
independence of W and B implies independence of Y_1 and Y_2.   
Let σ_1^2 and σ_2^2 denote the variances of Y_1 and Y_2, respectively. Due to (<ref>) and the fact that ∫_0^τ_1f^2(t)dt=1, see (<ref>), we then have

    σ_1^2+σ_2^2=1.

Put 

    α=inf_t∈[0, τ_1/2] |f'(t)|^2,   β=sup_t∈[0, τ_1/2] |f'(t)|^2

and note that 0< α≤β <∞, due to (<ref>). Since 

    σ_2^2 = ∫_t_0^t_1∫_t_0^t_1f'(s)· f'(t)·(t_1-max(s,t))(min(s,t)-t_0)t_1-t_0  ds dt

and [t_0,t_1]⊂ [0,τ_1/2] we conclude that

    α·(t_1-t_0)^312≤σ_2^2≤β·(t_1-t_0)^312.

Put

    n_0=⌈τ_12·(β6)^1/3-1⌉.

Using (<ref>), (<ref>) and (<ref>) we obtain that if n≥ n_0 then 

    α·τ_1^396(n+1)^3≤σ_2^2 ≤ 1/2 ≤σ_1^2,  σ_1^-2-1 =σ_2^2σ_1^2≤β·τ_1^348(n+1)^3.


Clearly, for all x≥ 1,

    G^p(x) =exp(
      x^2/2)(1+x^2)^1/2·ln^2 (2+x^2)≥exp(
      x^2/2)√(2)x·ln^2 (3x^2).

Moreover, G is differentiable on  with

    G'(x)=xp· G(x)·(1-1(1+x^2)- 4(2+x^2)·ln(2+x^2)).

Hence, for all x≥ 3,

    G'(x)≥x2p· G(x)>0.


Clearly, we may assume that n≥max(3,n_0). Let y_1∈ [n^3/2,2n^3/2] and y_2∈ [0,σ_2]. Then
y_1+y_2 ≥ y_1-y_2 ≥ n^3/2-σ_2≥ 3^3/2 - 1 >3, due to (<ref>). Hence, by (<ref>),

    |G(y_1+y_2)-G(y_1-y_2)|    ≥∫_y_1^y_1+y_2 G'(x)  dx ≥12py_1· y_2· G(y_1),

which jointly with (<ref>) yields

    |G(y_1+y_2)-G(y_1-y_2)|^p ≥1(2p)^p  y_1^p-1· y_2^p·exp(y_1^2/2)√(2)·ln^2(3y_1^2).

Employing (<ref>) and  (<ref>)  we conclude that

    [|G(Y_1+Y_2)-G(Y_1-Y_2)|^p] 
               ≥1/(2p)^p 2^3/2π·1/σ_1σ_2∫_n^3/2^2n^3/2∫_0^σ_2y_1^p-1y_2^p/ln^2(3y_1^2)·exp(-y_2^2/2σ_2^2-y_1^2/2(σ_1^-2-1))   dy_2  dy_1
               ≥1/(2p)^p 2^3/2π·σ_2^p/(p+1)√(e)∫_n^3/2^2n^3/2y_1^p-1/ln^2(3y_1^2)·exp(-y_1^2/2(σ_1^-2-1))    dy_1
               ≥1/(2p)^p 2^3/2π·σ_2^p/(p+1)√(e)·n^3p/2/ln^2(12n^3)·exp(-2n^3(σ_1^-2-1))
               ≥1/(2p)^p (p+1) 2^3/2π√(e)·(τ_1^3α/96)^p/2·(n/n+1)^3p/2·exp(-n^324(n+1)^3·βτ_1^3)/ln^2(12n^3)
               ≥(τ_1^3α)^p/2/2^5p+3/23^p/2 p^p (p+1)  π√(e)·exp(-βτ_1^324)·1/ln^2(12n^3).

Now combine (<ref>), (<ref>) and (<ref>) to complete the proof of Theorem <ref>.








§ PROOF OF THEOREMS <REF> AND <REF>
 

As  technical tools 
for the proof of Theorems <ref> and <ref> 
we employ the following two results for  centered Gaussian random variables. 


 
For every q∈ [0,∞) there exists κ_q∈ (0,∞) such that for every 
random variable Z∼𝒩( 0,  σ^2) with σ^2∈ [0, 14] and every 
a∈ [0,∞),

    [|Z|^q ·exp(a·|Z|+|Z|^2)]≤κ_q·σ^q· (1+a^q)·exp(a^2·σ^2).




Let q, a∈ [0,∞) and let Z∼𝒩( 0,  σ^2) with σ^2∈ [0, 14]. Without loss of generality we may assume that  σ^2>0. Let V∼𝒩( 0, 1).
 Then

    [|Z|^q ·exp(a·|Z|+|Z|^2)]
        =√(2)√(π)σ·∫_0^∞ x^q·exp(a x+x^2-x^22σ^2) dx
        =√(2)√(π)σ·exp(a^2σ^22-4σ^2)·∫_0^∞ x^q·exp(-1-2σ^22σ^2·(x-aσ^21-2σ^2)^2) dx
       ≤exp(a^2σ^22-4σ^2)·2  √(1-2σ^2)·[|σ√(1-2σ^2)· V + aσ^21-2σ^2|^q ]
       ≤exp(a^2σ^22-4σ^2)·2^q+1σ^q (1-2σ^2)^q+1/2·([|V|^q] + a^qσ^q(1-2σ^2)^q/2).

Note that  σ^2≤ 1/4 implies 1-2σ^2≥ 1/2 as well as σ^2/(1-2σ^2) ≤ 1/2,
which finishes the proof of the lemma. 



Let q∈[0,∞) and r∈ [0,12q) and let H∈ C^1(,) with

    sup_x∈|H'(x)|·exp(-q· x^2) < ∞.

Then there exists κ∈ (0,∞) such that for all  independent random variables V_1∼𝒩( 0,  v_1^2), V_2∼𝒩( 0,  v_2^2) with v_1^2+v_1^2 ≤ 1, 

    [|H(V_1+V_2)-H(V_1)|^r]≤κ· v_2^r.




Let q∈[0,∞) and r∈ [0,12q), let H∈ C^1(,) satisfy (<ref>) and let V_1∼𝒩( 0,  v_1^2), V_2∼𝒩( 0,  v_2^2) be independent with v_1^2+v_1^2 ≤ 1. Let U_1 and U_2 be independent standard normal random variables. By the properties of H there exists c∈ (0,∞) such that for all y,z∈,

    |H(y+z)-H(y)|≤∫_min(y,y+z)^max(y,y+z) |H'(x)| dx ≤ c· |z|·exp(q·
      (|y|+|z|)^2).

By the latter estimate, the Hölder inequality and the fact that v_1^2 + v_2^2 ≤ 1 we get 

    [|H(V_1+V_2)-H(V_1)|^r]    ≤ c^r· v_2^r·[|U_2|^r·exp(r· q·
      (v_1·|U_1|+v_2·|U_2|)^2)]
       ≤ c^r· v_2^r ·[|U_2|^r·exp(r· q·
      (U_1^2+U_2^2))] 
        = c^r· v_2^r·[|U_2|^r·exp(r· q·
      U_2^2)]·[exp(r· q·
      U_1^2)]
       ≤ c^r· v_2^r·([(1+|U_2|^r)·exp(r· q·
      U_2^2)])^2.

Note that r q< 1/2 and put v= (1-2rq)^-1/2. Then

    [(1+|U_2|^r)·exp(r· q·
      U_2^2)] = ∫_(1+|x|^r)√(2π)·exp(-x^22v^2)  dx = v·(1+v^r·[|U_1|^r] ),

which completes the proof of the lemma.



In the sequel we use the following notation. For n∈ we define B_n [ 0, τ_1] ×Ω→  by 

    B_n(t)=W(t)-W_n(t),   t∈ [0,τ_1],

and we put 

    Y_n=-∫_0^τ_1f'(t) B_n(t) dt,   Z_n= X_n, 2(T)

as well as

    σ_n^2 = Var(Y_n),  ν_n^2=Var(Z_n).

By Itô's formula and (<ref>) we have -a.s. 

    X_2(T)= Z_n+Y_n.


Let n∈ and ℓ∈. Then it is easy to check that

    Z_n,  Z_ℓ n-Z_n,  Y_ℓ n are  independent, centered, Gaussian random variables.

Moreover, using (<ref>) and Lemma <ref> we get

    Var(Y_ℓ n) + Var(Z_ℓ n)  = σ^2_ℓ n + ν_ℓ n^2 = 1,  Var(Z_ℓ n-Z_n)  = ν^2_ℓ n - ν^2_n,

and, proceeding as in the proof of (<ref>), it is easy to see that

    σ_ℓ n^2 ≤γτ_1^312 ℓ^2n^2,

where γ=sup_t∈[0, τ_1] |f'(t)|^2. 






We are ready to establish a p-th mean error estimate for the approximation X^∗_n,7(T).


There exists c∈ (0,∞)  such that for all n∈,

    [|      X_7( T ) -X^∗_n,7(T)    |^p]≤c/n^p.






Let n∈. Using (<ref>) we obtain

    [|      X_7( T ) -X^∗_n,7(T)    |^p]      =[|
          G(X_2(T)) -G(X^*_n, 2(T))
        |^p] 
          =∑_ℓ=1^∞[|
          G(Z_ℓ n+Y_ℓ n) -G(Z_ℓ n)
        |^p· 1_[a_ℓ, a_ℓ+1)(|Z_n|)].

It follows from (<ref>) that there exists c_1∈ (0,∞) such that 

    |G'(x)| ≤ c_1 ·|x|·exp(x^22p)

for all x∈. Hence, for all y,z ∈, 

    |G(z+y)-G(z)|≤∫_min(z,z+y)^max(z,z+y) |G'(x)| dx 
    ≤ c_1· |y|· (|z|+|y|)·exp(12p
      (|z|+|y|)^2),

which jointly with (<ref>) implies

    [|      X_7( T ) -X^∗_n,7(T)    |^p]
             ≤ c_1^p·∑_ℓ=1^∞[|Y_ℓ n|^p· (|Z_ℓ n|+|Y_ℓ n|)^p·exp(12
      (|Z_ℓ n|+|Y_ℓ n|)^2)· 1_[a_ℓ, a_ℓ+1)(|Z_n|)].

Note that for all ℓ∈,

    exp(12
      (|Z_ℓ n|+|Y_ℓ n|)^2)· 1_[a_ℓ, a_ℓ+1)(|Z_n|)
               ≤exp(12
      |Z_n|^2+a_ℓ+1·(|Z_ℓ n-Z_n|+|Y_ℓ n|)+|Z_ℓ n-Z_n|^2+|Y_ℓ n|^2)· 1_[a_ℓ, a_ℓ+1)(|Z_n|)

and

    (|Z_ℓ n|+|Y_ℓ n|)^p  
    ≤ 3^p· (1+|Z_n|^p)· (1+|Z_ℓ n-Z_n|^p)· (1+|Y_ℓ n|^p).

Hence, 

    [|      X_7( T ) -X^∗_n,7(T)    |^p]≤ (3c_1)^p·∑_ℓ=1^∞[A_ℓ,n· B_ℓ,n· C_ℓ,n],

where 

    A_ℓ,n   =(1+|Z_n|^p)·exp(12
      |Z_n|^2)· 1_[a_ℓ, a_ℓ+1)(|Z_n|),
    
      B_ℓ,n   =(1+|Z_ℓ n-Z_n|^p)·exp(a_ℓ+1· |Z_ℓ n-Z_n|+|Z_ℓ n-Z_n|^2),
    
      C_ℓ,n   =|Y_ℓ n|^p· (1+|Y_ℓ n|^p)·exp(a_ℓ+1·|Y_ℓ n|+|Y_ℓ n|^2)

for ℓ∈. Observe that (<ref>)  implies that for all ℓ∈,

    [A_ℓ,n· B_ℓ,n· C_ℓ,n] = [A_ℓ,n]·[ B_ℓ,n]·[ C_ℓ,n].


Next, put 

    n_1 = ⌈√(γτ_1^3)⌉.

Using (<ref>) and (<ref>) we see that  for all n≥ n_1 and ℓ∈,

    ν^2_ℓ n - ν^2_n = σ_n^2- σ_ℓ n^2 ≤σ_n^2 ≤γτ_1^312 n^2≤112.

Using (<ref>),  (<ref>) 
and Lemma <ref> we thus obtain that there exist κ_0,κ_p,κ_2p,c_2,c_3∈ (0,∞) such that for all n≥ n_1 and ℓ∈,

    [ B_ℓ,n]  ≤(2κ_0 + κ_p· (ν_ℓ n^2- ν_n^2)^p/2· (1+a_ℓ+1^p))·exp(a_ℓ+1^2· (ν_ℓ n^2- ν_n^2)) ≤ c_3·ln^p/2(ℓ+1)

and

    [ C_ℓ,n]  ≤(κ_p·σ_ℓ n ^p·  (1+a_ℓ+1^p) + κ_2p·σ_ℓ n ^2p· (1+a_ℓ+1^2p))·exp(a_ℓ+1^2·σ_ℓ n ^2)≤c_2(ℓ n)^p·ln^p(ℓ+1)·ℓ^13.

Furthermore, (<ref>) and (<ref>) jointly imply that 11/12≤ν_n^2 ≤ 1 for all n≥ n_1, and therefore there exists c_4∈ (0,∞) such that for all n≥ n_1 and ℓ∈,

    [ A_ℓ,n]     = 2√(2π)∫_a_ℓ/ν_n^a_ℓ+1/ν_n (1+(ν_n· x)^p)·exp(-x^22· (1-ν_n^2)) dx≤  (1+a_ℓ+1^p)· a_ℓ+1-a_ℓν_n
       ≤√(1211)( 1 + 2^pln^p/2(ℓ+1)
       )·2ℓ·ln^1/2(ℓ+1) ≤ c_4 ·ln^p-1/2(ℓ+1) ·1ℓ.

Hence, there exists c_5∈ (0,∞) such that for all n≥ n_1 and ℓ∈,

    [A_ℓ,n]·[ B_ℓ,n]·[ C_ℓ,n] ≤ c_5 ·1n^p·ln^2p-1/2(ℓ+1)ℓ^p+2/3.
 

Combining (<ref>), (<ref>) and (<ref>) we conclude that there exists c_6∈ (0,∞) such that for all n≥ n_1,

    [|      X_7( T ) -X^∗_n,7(T)    |^p] ≤ (3c_1)^p · c_5 ·1n^p∑_ℓ=1^∞ln^2p-1/2(ℓ+1)ℓ^p+2/3≤ c_6 ·1n^p.


In view of Lemma <ref> it remains                 
to prove that for all n<n_1,

    [|G(X^*_n, 2(T))
        |^p] < ∞.


To this end we define ρ→ [3,∞) by ρ(x) = max(|x|,3). Clearly, ρ is convex. Moreover, by (<ref>) and (<ref>) we obtain that G as well as G' are increasing on [3,∞). In particular, G is convex on [3,∞). Using the monotonicity and convexity of G as well as the convexity of ρ we conclude that G∘ρ is convex.  

For n,ℓ∈  put ℱ_ℓ n = σ({W(iτ_1/(ℓ n)) i = 1,…, ℓ n}) and note that Z_ℓ n = [X_2(T)|  ℱ_ℓ n ]. Using the estimate G(x)≤ (ln(2))^-2/pexp(x^2/2p) and the Jentzen inequality we therefore obtain that for all n,ℓ∈

    |G(Z_ℓ n)|^p ·_[a_ℓ, a_ℓ+1)(|Z_n|)
           ≤(|G(ρ(Z_ℓ n))|^p+(ln(2))^-2exp(9/2)) ·_[a_ℓ, a_ℓ+1)(|Z_n|)
           ≤([|G(ρ(X_2(T)))|^p|  ℱ_ℓ n ] +(ln(2))^-2exp(9/2))·_[a_ℓ, a_ℓ+1)(|Z_n|)
            =  [|G(ρ(X_2(T)))|^p _[a_ℓ, a_ℓ+1)(|Z_n|)|  ℱ_ℓ n] +(ln(2))^-2exp(9/2)·_[a_ℓ, a_ℓ+1)(|Z_n|).

Hence there exists c_7∈ (0,∞) such that for all n∈,

    |G(X^*_n, 2(T))|^p ≤ c_7·(∑_ℓ=1^∞ [|G(ρ(X_2(T)))|^p _[a_ℓ, a_ℓ+1)(|Z_n|)|  ℱ_ℓ n] +1),

which implies

    [|G(X^*_n, 2(T))|^p]  ≤ c_7·([|G(ρ(X_2(T)))|^p] + 1).

Finally, note that G(ρ(X_2(T)))≤ G(X_2(T)) + (ln(2))^-2/pexp(9/2p) and apply Lemma <ref> to complete the proof of (<ref>).


Next, we provide error estimates for the approximations X_n,2(T),X_n,3(T),X_n,5(T) and X_n,7(T). 

 Let r_2,r_3∈ (0,∞), r_5∈ (0,2p) and r_7∈ (0,p). Then there exists c∈ (0,∞) such that for every i∈{2,3,5,7} and every n∈,

    [|X_i(T)-X_n,i(T)|^r_i]≤c/n^r_i.




Let r_2,r_3∈ (0,∞), r_5∈ (0,2p) and r_7∈ (0,p). Let n∈. 
In all of the four cases we apply Lemma <ref> with V_1 = X_n,2(T) = Z_n and V_2=Y_n, see (<ref>). Thus Var(V_1) +  Var(V_2) = 1, and according to (<ref>) we have Var(V_2) ≤ (γτ_1^3)/(12n^2).
Moreover, for i∈{2,3,5,7} we use the function H=H_i in Lemma <ref>, where H_2,H_3,H_5,H_7→ are given by

    H_2(x) = x,   H_3(x) = x^2,   H_5(x) =exp(14px^2),   H_7(x) =
    G(x).

Let 

    q_2=0,    q_3∈ (0,1/(2r_3)),   q_5∈ (1/(4p),1/(2r_5)),   q_7∈ (1/(2p),1/(2r_7)).

Employing (<ref>) in the case i=7 we then see that there exists c∈ (0,∞) such that for every i∈{2,3,5,7} and every x∈,

    |H_i'(x)| ≤ c·exp(q_i· x^2),

which completes the proof.



Clearly, Lemmas <ref> and <ref> jointly yield the error estimates in Theorems <ref> and <ref>.


It remains to establish the cost estimate in Theorem <ref>. 

Let n∈.
Clearly, if ν_n=0 then X_n,2(T)=Z_n=0 a.s. and we have cost(X^*_n(T))  = n a.s. Next, assume ν_n^2 >0. Using (<ref>) and the fact that ν_n^2≤ 1 we get for every l∈, 

    ({|Z_n|∈  [a_ℓ, a_ℓ+1)})     =2√(2π)ν_n∫_a_ℓ^a_ℓ+1exp(-x^22ν_n^2)dx≤2√(2π)ν_n·exp(-a_l^22ν_n^2)· (a_ℓ+1-a_ℓ)
       ≤1ν_n·√(2)√(π)·exp(-2ln(ℓ))·2√(ln(2))·ℓ≤1ν_n·2^3/2√(πln(2))·1ℓ^3.

Hence 

    [cost(X^*_n(T))] =  
    ∑_ℓ=1^∞ℓ· n·({|Z_n|∈ [a_ℓ, a_ℓ+1)})≤nν_n·√(2)√(πln(2))·∑_ℓ=1^∞1ℓ^2.

Finally note that lim_n→∞ν_n^2 = 1, due to (<ref>) and (<ref>), and therefore inf_nν_n >0ν_n > 0, which completes the proof of the cost estimate and finishes the proof of Theorems <ref> and <ref>. 





§ DISCUSSION



The key contribution of this paper is to show that even then when an autonomous SDE on [0,T] has smooth coefficients with first order derivatives of at most linear growth and its solution X satisfies [sup_t∈ [0,T] |X(t)|^p]< ∞, where p∈ [1,∞), it may happen that X(T) can not be approximated on the basis of finitely many observations of the driving Brownian motion at fixed times in [0,T] with a polynomial p-th mean error rate, see Theorem <ref>.
This result naturally leads to a number of questions related to possible extensions or tightenings with respect to the class of approximations, the speed of convergence, the moment conditions on the solution and the polynomial growth conditions on the first order derivatives of the coefficients. 

Does there exist an SDE of the above type such that a sub-polynomial rate of convergence holds for any adaptive approximation as well? For the SDE considered in the present paper, there is an adaptive method, which achieves a polynomial error rate, see Theorem <ref>.

Does there exist an SDE of the above type such that the smallest possible p-th mean error  that can be achieved by any non-adaptive 
method based on n evaluations of the driving Brownian motion
or even 
by any
adaptive method based on n evaluations of the driving Brownian motion on average converges to zero slower than a given arbitrarily slow decay in terms of n? A negative result of this type is true for the class of  SDEs with bounded smooth coefficients, see (<ref>) and <cit.>.

The first order derivatives of the coefficients of the pathological SDE (<ref>) constructed in the present paper are of at most linear growth. 
Can a sub-polynomial rate of convergence of the smallest possible p-th mean error also
occur when the first order derivatives of the coefficients are of at most polynomial growth with an exponent α∈ (0,1)?

Finally it is open, whether a sub-polynomial rate of convergence of the smallest possible p-th mean error can also occur when the solution X has finite moments of some order q>p or even satisfies [sup_t∈[0, T]|X(t)|^q] < ∞ for all q≥ 1. The pathological SDE (<ref>) satisfies [sup_t∈[0, T]|X(t)|^q] < ∞ only for q≤ p,
    see Lemma <ref>.
  


The key contribution of this paper is to show that a sub-polynomial rate of convergence may happen even then when  the derivatives of the coefficients are of at most polynomial growth, at least if non-adaptive methods are considered. There are still, however, a number of open questions with respect to negative results for such SDEs, which we would like to address in the future work.
 Does there exist an SDE with smooth coefficients that have at most polynomially growing derivatives and a solution X satisfying the moment condition (<ref>) such that a sub-polynomial rate of convergence holds for any adaptive approximation as well? Can one choose an SDE from this class in such a way that the smallest possible absolute mean error that can be achieved by any non-adaptive and eventually by any adaptive method converges to zero slower than a given arbitrarily slow rate of convergence, as it is the case for the class of  SDEs with bounded smooth coefficients, see (<ref>) and <cit.>? 
The derivatives of the coefficients of the actual SDE (<ref>) are of at most linear growth. Can a sub-polynomial rate of convergence

happen when the derivatives of the coefficients are of at most polynomial growth of order α, where α∈ (0,1)? Note that if α=0 then the coefficients are globally Lipschitz continuous.
Can a sub-polynomial rate of convergence happen under 

a stronger moment condition  [sup_t∈[0, T]|X(t)|^q] < ∞ for some q>1, which is not satisfied by the solution of the actual SDE (<ref>)?



 





acm


