CONSISTENCY AND ASYMPTOTIC NORMALITY OF STOCHASTIC EULER SCHEMES FOR
ORDINARY DIFFERENTIAL EQUATIONS
JOHANNES T. N. KREBS

arXiv:1609.06880v1 [math.PR] 22 Sep 2016

Abstract. General stochastic Euler schemes for ordinary differential equations are studied. We give proofs on the
consistency, the rate of convergence and the asymptotic normality of these procedures.

1. Introduction
We study the consistency and asymptotic normality of stochastic Euler schemes which are designed to
approximate ordinary differential equations. Euler schemes are often used to simulate stochastic differential
equations. Fierro and Torres [2001] study the consistency of these schemes in the context of Itô stochastic
differential equations. However, this idea can be used to approximate ordinary differential equations, too:
Fierro and Torres [2007] consider a special kind of Euler approximation for a given ODE. In this paper, we
generalize the idea: Let there be given the ODE system ẋ = F(t, x), x(0) = x0 ∈ Rd , t ∈ [0, T ], 0 < T <
∞. Then we approximate the solution x on a partition πN of [0, T ] with a stochastic Euler scheme that is
based on random variables F̃kN instead on F. This approach can be useful in applications where one aims at
approximating the trajectory of such a solution x for a function F which is costly to evaluate, for instance, in
P
the case where F is the sum of (finitely) many single functions fi , i ∈ I, i.e. F = i∈I fi . The paper is organized
as follows: In Section 2 we introduce the basic notions and regularity conditions of the model. In Section 3
we give consistency results for our general Euler scheme. We state results on the asymptotic normality of the
procedure in Section 4. Appendix A contains some background material.
2. Preliminaries
We denote for p ≥ 1 by k · k p the p-norms on the d-dimensional Euclidean space. Let T ∈ R+ be a finite
time horizon and let F = (F1 , . . . , Fd )′ : [0, T ] × Rd → Rd be a continuous vector valued function. F fulfills
the following growth conditions w.r.t. the first and second coordinate for s, t ∈ [0, T ] and for x, y ∈ Rd
kF(s, x) − F(t, x)k1 ≤ K1 (1 + kxk1 ) |s − t|,

kF(t, x) − F(t, y)k1 ≤ K2 ||x − y||1 ,

(2.1)

(2.2)

where 0 < K1 , K2 < ∞ are some positive constants. Let there be given the ODE ẋ = F(t, x) andR x(0) = x0 ∈ Rd
t
on [0, T ]. Denote the unique global solution of this equation by x : [0, T ] → Rd , x(t) := x(0)+ 0 F (s, x(s)) ds.
This solution is guaranteed by the global Lipschitz condition (2.2) and is Lipschitz-continuous with a Lipschitzconstant 0 < C < ∞, i.e. kx(s) − x(t)k1 ≤ C|s − t|. Next, choose a sequence of partitions, πN , N ∈ N+ , of
the interval [0, T ] such that πN consists of the points t0N = 0 < t1N < . . . < tKNN = T and such that the mesh
N
of the partition ∆N := max1≤k≤KN ∆kN converges to zero as N → ∞, where ∆kN := tkN − tk−1
. The stochastic
part is introduced via a probability space (Ω, A, P) endowed with the following mappings: For N ∈ N+ and
k = 1, . . . , KN the function
h 

 i
N
N ′
F̃kN = (F̃k,1
, . . . , F̃k,d
) : [0, T ] × Rd × Ω → Rd is measurable B [0, T ] × Rd ⊗ A B Rd
and is Lipschitz-continuous w.r.t. the second coordinate with the same Lipschitz constant as F.
Furthermore, for any selection of time-space coordinates (t1 , y1 ), . . . , (tKN , yKN ) ∈ [0, T ] × Rd the random variables F̃1N (t1 , y1 ), . . . , F̃ KNN (tKN , yKN ) are independent and each F̃kN is an unbiased estimator of F in the sense
h
i
that E F̃kN (t, y) = F(t, y) for (t, y) ∈ [0, T ] × Rd . In addition, we assume that there exists a constant
Date: December, 1 2015.
2010 Mathematics Subject Classification. Primary: 60H10; secondary 34F05, 93E03.
Key words and phrases. Stochastic Euler schemes; ordinary differential equations; consistency; rate of convergence; asymptotic
normality.
The author gratefully acknowledges the financial support of the Fraunhofer ITWM which is part of the Fraunhofer-Gesellschaft zur
Förderung der angewandten Forschung e.V.
1

2

JOHANNES T. N. KREBS

0 < K3 < ∞ such that for each ht ∈ [0, T ], ai = 1, . . . , d, k = 1, . . . , KN and N ∈ N+ the variance of the
N
approximation is bounded as Var F̃k,a
(t, x(t)) ≤ K3 . We generate for each N ∈ N+ a stochastic sequence
o
n  
N
N N
x̂ = x̂ ti : i = 0, . . . , KN according to the rule
 
 

 
 
N
N
N
+ ∆iN F̃iN ti−1
, x̂N ti−1
for i = 1, . . . , KN .
(2.3)
x̂N t0N := x(0) ∈ Rd and x̂N tiN := x̂N ti−1
o
n  
We pass from this sequence x̂N tiN : i = 0, . . . , KN to a right-continuous process which we denote again by
x̂N , namely, we define
h
 
 

N
(2.4)
for i = 0, ..., KN − 1 and x̂N (T ) = x̂N tKNN .
x̂N (t) := x̂N tiN for t ∈ tiN , ti+1
n
o
In the following, when speaking of x̂N , we shall always refer to this càdlàg process. Moreover, F N ( · ) : N ∈ N+
is a sequence of filtrations on (Ω, A, P) such that for each N ∈ N+ the filtration F N ( · ) is the natural and rightcontinuous filtration of the process x̂N from equation (2.4).
3. Consistency and Rate of Convergence
We come to the first main result of this paper, this is the convergence in mean of the processes x̂N , N ∈ N+ ,
namely
Theorem 3.1 (L2 -convergence of x̂N to x). Let the sequence of stochastic processes ( x̂N : N ∈ N+ ) be defined
in equations (2.3) and (2.4). Let x be the unique global solution to the ordinary differential equation. Then,
there exists a constant 0 < B < ∞ such that
√
≤ B ∆N .
sup x̂N (t) − x(t) 1

P

t∈[0,T ]

L2 ( )

Proof. Throughout the proof we shall write k · k for the Euclidean 1-norm on Rd . Furthermore, we set xkN :=
 
 
xN tkN and x̂kN := x̂N tkN , for k = 0, . . . , KN . First, we consider x̂N at the points tkN , k = 1, . . . , Kn . We derive
for the difference x̂kN − xkN at each k = 1, . . . , KN the equation
n 


o
n 


o
N
N
N
N
N
N
N
N
N
N
x̂kN − xkN = x̂k−1
− xk−1
+ F̃kN tk−1
, x̂k−1
− F̃kN tk−1
, xk−1
∆kN + F̃kN tk−1
, xk−1
− F tk−1
, xk−1
∆kN


Z






 N
N
N
(s,
F
x(s))
ds
F
t
,
x
∆
−
+

.
 k−1 k−1 k


∆N
k

Successive iteration down to t0N yields
x̂kN − xkN =

k n
X
j=1

+

k n
X



o



o
F̃ Nj tNj−1 , x̂Nj−1 − F̃ Nj tNj−1 , xNj−1 ∆Nj +
F̃ Nj tNj−1 , xNj−1 − F tNj−1 , xNj−1 ∆Nj
j=1



Z





 N
N
N
.
F(s, x(s)) ds
F t j−1 , x j−1 ∆ j −





∆N

k 
X
j=1

(3.1)

j

By the growth condition w.r.t. the time coordinate and the Lipschitz condition w.r.t. the space coordinate, we
have for the last term in (3.1)
(
!
) 
Z


2
N
N
F t j−1 , x j−1 − F(s, x(s)) ds ≤ K1 1 + sup kx(t)k + K2C ∆Nj .
∆Nj

t∈[0,T ]



We put for short L := K1 1 + supt∈[0,T ] kx(t)k + K2C. We can estimate the left-hand side of (3.1) using the
Lipschitz condition on the stochastic approximations F̃kN of F to arrive at the following bound for x̂kN − xkN :
x̂kN − xkN ≤ K2

k
X
j=1

x̂Nj−1 − xNj−1 ∆Nj +

k 
X
j=1

k
X




 2
F̃ Nj tNj−1 , xNj−1 − F tNj−1 , xNj−1 ∆Nj +
L ∆Nj .

(3.2)

j=1

We apply the discrete Gronwall inequality from Lemma A.1 from Appendix A to the bound given in (3.2). We
get
x̂kN − xkN ≤

k 
X
j=1

k
X




 2
F̃ Nj tNj−1 , x j−1 − F tNj−1 , xNj−1 ∆Nj +
L ∆Nj
j=1

CONSISTENCY AND ASYMPTOTIC NORMALITY OF STOCHASTIC EULER SCHEMES FOR ORDINARY DIFFERENTIAL EQUATIONS 3


 k−1
 j

j 
k−1  X
X
X

 X
 



 
o

n

N
N
N N
N
N
N
N 2
N
K2 ∆i 
+
F̃i ti−1 , xi−1 − F ti−1 , xi−1 ∆i + L
∆i 
K2 ∆ j exp 





j=1

i=1

≤ M1 ∆N +

i= j+1

i=1

k 
X
j=1





F̃ Nj tNj−1 , xNj−1 − F tNj−1 , xNj−1 ∆Nj

(3.3)



j 


k−1 X


X







N
N
N N
N
N
N
F̃
t
,
x
∆
−
F
t
,
x
,
+ M2 
∆
j 
i
i
i−1 i−1
i−1 i−1





 j=1 i=1

where the constants M1 and M2 are given by M1 := LT + K2 LT 2 exp(K2 T ) and M2 := K2 exp(K2 T ). In
particular, for A := 2M12 and B := 2(1 + M2 T )2 it holds good that
sup
1≤ j≤KN

x̂Nj

−

2
xNj



≤A ∆


N 2

+ B sup
1≤ j≤KN

j 
X

2

F̃iN

i=1



N
N
ti−1
, xi−1





N
N
− F ti−1
, xi−1
∆iN

.

(3.4)

h
i
Next, we use the independence assumptions on the F̃kN and the assumption that in each point E F̃kN (t, x) =
F(t, x). We show that the discrete process
n

Kn
X
o
 
 

 
N
N
N
N
t0N , . . . , tKNN ∋ tNj 7→
1ntN ≤tN o F̃iN ti−1
, x ti−1
− F ti−1
, x ti−1
∆iN
i

i=1

j

constitutes a submartingale[F N ( · )]. Indeed, we have for any two 1 ≤ j ≤ k ≤ KN


 k
 d k
 X  
 X X 
  




  



N
N
N
N
N
N
N
N
N
, xi−1
ti−1
, xi−1
F̃i,a
∆iN F N tNj  .
− Fa ti−1
, xi−1
F̃iN ti−1
− F ti−1
, xi−1
∆iN F N tNj  = E 
E 
a=1 i=1

i=1

Due to the independence assumption on the stochastic family F̃iN , the 1-dimensional processes
n

KN
X

 

 

o
N
N
N
N
N
, x ti−1
ti−1
, x ti−1
1ntN ≤tN o F̃i,a
∆iN
− Fa ti−1
t0N , ..., tKNN ∋ tNj 7→
i=1

i

j

are submartingales[F N ( · )] for each a = 1, . . . , d. Summation over the index a proves the statement about the
submartingale property. This puts us in position to use Doob’s L p -Inequality for equation (3.4) with p = 2
applied to the above submartingale

 k
2 
#
"

 X  
 




N 2
N
N 2
N
N
N
N
N
N
E sup x̂k − xk ≤ A(∆ ) + B E  sup  F̃i ti−1 , xi−1 − F ti−1 , xi−1 ∆i  
(3.5)
1≤k≤KN
1≤k≤KN
i=1

2 
KN 
  X
 





N
N
N
N
F̃iN ti−1
, xi−1
− F ti−1
, xi−1
∆iN  
(3.6)
≤ A(∆N )2 + 4B E  
i=1

2
KN 
d

 X
X





N
N
N
N
N
N
N 2
E  F̃i,a ti−1 , xi−1 − Fa ti−1 , xi−1 ∆i 
≤ A(∆ ) + 4Bd
= A(∆N )2 + 4Bd

≤ A(∆N )2 +

a=1

i=1

KN 
d X
X

∆iN

a=1 i=1
4BT d2 K3 ∆N .

2

h

i
N
N
N
Var F̃i,a
ti−1
, xi−1

(3.7)

(3.8)

p
The first inequality (3.5) follows immediately from inequality (3.4). Inequality (3.6)
stems
 L - 


  from Doob’s
N
N
N
N
N
inequality. Equality (3.7) follows from the indepence of the random variables F̃1,a t0 , x t0 , . . . , F̃ KN ,a tKN −1 , x tKNN −1 .
The last inequality (3.8) follows from the condition that the variance of the approximation is uniformly
bounded. We are
to
x̂N over the entire interval [0, T ]. Remember
 now
 in position
h
 consider the processes
 
N
N
N
N N
N
N N
that x̂ (t) = x̂ tk−1 for t ∈ tk−1 , tk and x̂ (T ) = x̂ tN , thus,
(
 
  2
 2 )
2
sup x̂N (t) − x(t) ≤ 2 sup x̂N tkN − x tkN
.
(3.9)
+ C 2 ∆N
t∈[0,T ]

1≤k≤KN

4

JOHANNES T. N. KREBS

 1
All in all, we find that supt∈[0,T ] x̂N (t) − x(t) L2 (P) ≤ const ∆N 2 for a sequence of partitions having a mesh
∆N which converges to zero. This finishes the proof.

In addition to the L2 (P)-convergence of the process x̂N , nwe can state another
o result on the pathwise conN
vergence for a special choice of the partitioning sequence π : N = 1, . . . , ∞ . It is an application of Kolmogorov’s maximal inequality and follows immediately from the inequality from equation (3.4). We have the
following theorem
n
o
Theorem 3.2 (a.s.-convergence of x̂N ). Let πN : N = 1, . . . , ∞ be a partitioning sequence of the interval
P
N
N
[0, T ] such that ∞
N=1 ∆ < ∞. Then supt∈[0,T ] x̂ (t) − x(t) 1 converges to zero almost surely.
 
 
Proof. Write again xkN := x tkN and x̂kN := x̂N tkN for k = 0, . . . , KN . Consider equation (3.4), the maximum
on the right-hand side can be bounded as


j 
j 
d 
X
X
X










N
N N
N
N
N
N
N
N
N
N
N
 max
max
F̃i ti−1 , xi−1 − F ti−1 , xi−1 ∆i ≤
F̃i,a ti−1 , xi−1 − Fa ti−1 , xi−1 ∆i  .
1≤ j≤KN
1≤ j≤KN
i=1

a=1

1









i=1



Pj
N
N
N
N
N
, xi−1
∆iN → 0 almost surely for each coordinate
ti−1
, xi−1
− Fa ti−1
F̃i,a
We show that max1≤ j≤KN i=1
a = 1, . . . , d. An application of Kolmogorov’s maximal inequality yields for ε > 0 that


j 
KN
X




  K3 T




1 X
N
N
N
N
N
N
N
N
N

ti−1
, xi−1
Var F̃i,a
∆iN ≤ 2 ∆N .
P 1≤max
F̃i,a ti−1 , xi−1 − Fa ti−1 , xi−1 ∆i > ε ≤ 2
j≤KN
ε
ε
i=1
i=1

Hence, we conclude the a.s.-convergencenfrom the first Borel-Cantelli
Lemma by the convergence assumption
o
on the meshes of partitioning sequence πN : N = 1, . . . , ∞ . The conclusion follows immediately by combining inequality (3.4) and (3.9), as well as the fact that almost sure convergence is unaffected by continuous
transformations.

4. Asymptotic Normality of Stochastic Approximation Procedures
In this section we prove the asymptotic normality of the stochastic Euler schemes for ODE approximations
Theorem 4.1. Let {πN : N ∈ N+ } be the sequence of dyadic partitions of [0, T ], i.e. πN = {T k/2N : k =
0, 1, . . . , 2N }. Let F = (F1 , . . . , Fd ) fulfill the regularity conditions from (2.1) and (2.2). Additionally, let each
component of F be continuously differentiable w.r.t. the space coordinate, i.e. (t, x) 7→ ∇ x Fi (t, x) is continuous
for i = 1, . . . , d.
Furthermore, let the stochastic approximations F̃kN be regular in that for all N ∈ N+ and k = 1, . . . , 2N the F̃kN
are independent copies of F̃ where the time-space process F̃ : [0, T ] × Rd × Ω → Rd is Lipschitz-continuous
in the space coordinate with the Lipschitz constant K2 as well as continuous in the time coordinate and fulfills
the integrability condition
#
"
′ 2
E sup F̃(t, x(t)) · F̃(t, x(t)) 1 < ∞.
t∈[0,T ]

 − 1 

Then for each t ∈ [0, T ] in the limit limN→∞ ∆N 2 x̂N (t) − x(t) ∼ N(0, Σ(t)), where the function Σ : [0, T ] →
Rd×d is defined as
Z t
i
h
Σ(t) =
P(s, t)E (F̃(s, x(s)) − F(s, x(s))) · (F̃(s, x(s)) − F(s, x(s)))′ P(s, t)′ ds
0

and P is the uniform limit of the function PN on [0, T ]2 given by [0, T ]2 ∋ PN (s, t) =

Q

s<t Nj ≤t




 
I + ∆N ∇ x F tNj−1 , x tNj−1 .

Proof. We write k · k throughout the proof for the 2-norm; since any two norms on the Euclidean space are
equivalent, bounds and estimates w.r.t. the 1-norm can be multiplied with the corresponding equivalence
constant and are thus valid w.r.t. the 2-norm, too. For a matrix A, denote by kAk := sup x:kxk≤1 kAxk the spectral
norm of A. We use the abbreviations

 
 
 − 1 
Z N := ∆N 2 x̂N − x as well as xkN := x tkN and x̂kN := x̂N tkN

CONSISTENCY AND ASYMPTOTIC NORMALITY OF STOCHASTIC EULER SCHEMES FOR ORDINARY DIFFERENTIAL EQUATIONS 5

h

N
for simplicity. Choose t ∈ [0, T ] arbitrary but fix, w.l.o.g. t ∈ tkN , tk+1
, if we add the virtual point t2NN +1 in case
that t = T . Then
Z t



 Z tkN
N
N
N
N
N
N
N N N
N
F(s, x(s)) ds
x̂ (t) − x(t) = x̂k − xk + xk − x(t) = x̂k−1 − xk−1 + ∆ F̃k tk−1 , x̂k−1 −
F(s, x(s)) ds −
tkN

tN


 k−1 
i
N
N
N
N
N
N
N N
N
N
N
= I + ∆ ∇ x F tk−1 , xk−1 x̂k−1 − xk−1 + ∆ F̃k tk−1 , xk−1 − F tk−1
, xk−1
h 


  


i
N
N
N
N
N
N
N
N
+ ∆N F̃kN tk−1
, x̂k−1
− F tk−1
, x̂k−1
− F̃kN tk−1
, xk−1
− F tk−1
, xk−1
h 





i
N
N
N
N
N
N
N
N
, x̂k−1
+ ∆N F tk−1
− F tk−1
, xk−1
− ∇ x F tk−1
, xk−1
x̂k−1
− xk−1
Z tN 
Z t

k
N
N
F(s, x(s)) ds
F tk−1
, xk−1
+
− F(s, x(s)) ds −
h



i 



h

tkN

N
tk−1

We make the following definitions




N
N
N
N
mkN := F̃kN tk−1
, xk−1
− F tk−1
, xk−1
,
h 


  


i
N,k
N N
N
N
N N
N
N
N
N
N
R1 := ∆ F̃k tk−1 , x̂k−1 − F̃k tk−1 , xk−1
− F tk−1
, x̂k−1
− F tk−1
, xk−1
,
h







i
N
N
N
N
N
N
N
N
, x̂k−1
R2N,k := ∆N F tk−1
− F tk−1
, xk−1
− ∇ x F tk−1
, xk−1
x̂k−1
− xk−1
,
Z
Z tN 
t

k
N
N
F(s, x(s)) ds.
F tk−1
, xk−1
− F(s, x(s)) ds and R4N := −
R3N,k :=
tkN

N
tk−1

Set RN,k := R1N,k + R2N,k + R3N,k ; note that |R4N | ≤ C∆N , for a constant 0 < C < ∞. Thus, we get Z N (t) =
1
Z N (tkN ) + (∆N )− 2 R4N and at the partitioning points, we face the following structure
 − 1
  h

    12
i
N
N
N
Z N tkN = I + ∆N ∇ x F tk−1
, xk−1
Z N tk−1
+ ∆N mkN + ∆N 2 RN,k for 0 < tkN ≤ T and Z N (0) = 0.

Consequently, successive iteration yields








X 
Y 





  N  21 N  N − 21 N,k
N
N
N
N
+ R4N .
m
+
∆
R
Z (t) =
∇
F
t
,
x
I
+
∆
∆


x
j
j−1
j−1 
k





N
N
 N N

k:t0 <tk ≤t

(4.1)

j:tk <t j ≤t

In the sequel, we prove that the sum which involves the mkN tends to the desired normal distribution, whereas
the sum involving the remainder RN,k tends to zero in probability. Hence, Z N (t) is asymptotically normally
distributed with the same parameters. Consider the first sum, we use the definitions
Y n

o   1
U N,k :=
I + ∆Nj ∇ x F tNj−1 , xNj−1 ∆N 2 mkN for 0 < tkN ≤ t
j:tkN <t Nj ≤t

and U N := 0<tkN ≤t U N,k . Note that for N ∈ N+ the random variables U N,1 , . . . , U N,2N are independent.
W.l.o.g., assume that (Ω, A, P) is endowed with independent normal distributions YN,k such that YN,k ∼

P

N 0, Cov U N,k , U N,k for k = 1, . . . , 2N . Set YN := 0<tkN ≤t YN,k . We prove that the difference of the characteristic functions ϕUN − ϕYN convergences pointwise to zero: For a fix α ∈ Rd , we show that ϕUN (α) − ϕYN (α) → 0
as N → ∞. Therefore, we use the fundamental inequality
X
ϕUN,k (α) − ϕYN,k (α) C .
(4.2)
ϕUN (α) − ϕYN (α) C ≤
P

k:0<tkN ≤t

An application of Lemma A.2 yields

X
(4.2) ≤ 2 kαk2
E UN,k
k:0<tkN ≤t

+ 2 kαk2

X

k:0<tkN ≤t

E



2

YN,k


X
1{kαk kUN,k k>ε/2} + ε kαk2

E

k:0<tkN ≤t

2



1{kαk kYN,k k>ε/2} + ε kαk2

X

k:0<tkN ≤t



E

U N,k


YN,k

2


2



(4.3)

We show that the first and the third sum of (A.2) converge to zero as N → ∞ for any ε > 0. This implies
that the second and the fourth sum are bounded, and, when multiplied by ε, become small, too. We intend to

6

JOHANNES T. N. KREBS
2

bound U N,k , it is
 1
U N,k ≤ ∆N 2

Y 

j:tkN <t Nj ≤t

1 + ∆N k∇ x F( · , x( · ))k∞



 1
mkN ≤ ∆N 2 exp (T k∇ x F( · , x( · ))k∞ ) mkN .

(4.4)

We consider the first sum of (4.3): Using (4.4), we arrive at
X

E

k:0<tkN ≤t



U N,k

2



o

n

1{kUN,k k≥ε} = exp 2T k∇ x F( · , x( · ))k∞ ∆

N

X



E  mkN

2

1(

1

kmkN k≥exp(−T k∇x F( · ,x( · ))k∞ )ε(∆N )− 2




2
2
)
 ,
≤ c T E  sup F̃(t, x(t)) − F(t, x(t)) 1(
1
−
supt∈[0,T ] kF̃(t,x(t))−F(t,x(t))k ≥c−1 ε(∆N ) 2 
t∈[0,T ]
(4.5)
k:0<tkN ≤t

where c := exp (T k∇ x F( · , x( · ))k∞ ). An application of Lebesgue’s dominated convergence theorem yields
that (4.5) converges to zero as N converges to infinity. We obtain for the third sum in equation (4.3)

E

X

k:0<tkN ≤t

h

α, YN,k

2

d

1
X X
i
(i) 4 2
E YN,k
1{|hα,YN,k i|≥ε} ≤ kαk2
k:0<tkN ≤t i=1

P



α, YN,k ≥ ε

 21

(4.6)

.

Since, the d elements of the vector YN,k are normally distributed, we achieve with the notation ΣN,k for the

1

√ 
P
P √ N,k
2
(i) 4 2
′
= 3E U N,k
≤ const ∆N , with
covariance matrix Cov(U N,k U N,k
) that di=1 E YN,k
= di=1 3Σi,i
 D
E
the help of equation (4.4). In addition, since α, YN,k ∼ N 0, α, ΣN,k α , we get

P



α, YN,k ≥ ε

 12

≤

√

 D

E− 1  12
2Φ −ε α, ΣN,k α 2 ≤ exp −ε2 /4 kαk−2 ΣN,k

−1



,



2
≤ const ∆N from equation
with the help of a bound given in Chiani et al. [2003]. And ΣN,k ≤ E U N,k
(4.4). This proves that (4.6) converges to zero as N tends to infinity. Consequently, ϕUN (α) − ϕYN (α) → 0, for
any α ∈ Rd .
Clearly YN ∼ N(0, ΣN ), where ΣN = Cov(U N , U N ) and can be written as



′
X  Y 
 ′ i  Y 

 h

 


N
ΣN =
I + ∆Nj ∇ x F tNj−1 , xNj−1  E mkN mkN 
I + ∆Nj ∇ x F tNj−1 , xNj−1  tkN − tk−1

 N N


k:0<tkN ≤t j:tkN <t Nj ≤t
j:tk <t j ≤t
X


  



′ 
′ i


 h 
N
PN tkN , t tkN − tk−1
, (4.7)
=
PN tkN , t E F̃ tkN , xkN − F tkN , xkN · F̃ tkN , xkN − F tkN , xkN
k:0<tkN ≤t




Q
with the notation PN (s, t) = j:s<tNj ≤t I + ∆Nj ∇ x F tNj−1 , xNj−1 . Due to the continuity of t 7→ ∇ x F(t, x(t)), we
get with the help of Lemma A.3 that PN converges uniformly on [0, T ] to a continuous matrix valued function
P. An application of Lebesgue’s dominated convergence theorem yields that the map which is defined from
the factor in the middle of (4.7) as
h
 
′ i
Γ : [0, T ] → Rd×d : t 7→ E F̃(t, x(t)) − (t, x(t)) · F̃(t, x(t)) − (t, x(t))
Rt
is continuous, thus, ΣN converges uniformly on [0, T ] to 0 P(s, t) Γ(s) P(s, t)′ ds.

 Rt
All in all, YN converges to N 0, 0 P(s, t)Γ(s)P(s, t)′ ds in law. It remains to prove that the summed error terms
in (4.1) converge to zero in probability.
E i error term. Note that due to the independence,
hD 
 We startwith the first
we have for all j , k that E PN tNj , t R1N, j , PN tkN , t R1N,k = 0. Hence, we obtain

2


X
Y
1







N,k
N N
N
N −2
E  ∆
I + ∆ j ∇ x F t j , x j R1



N
N N
k:0<tk ≤t j:tk <t j ≤t

N

≤ ∆ exp (2T k∇ x F( · , x( · ))k∞ )

2N
X
k=1

E

 




  



F̃kN tkN , x̂kN − F̃kN tkN , xkN − FkN tkN , x̂kN − FkN tkN , xkN

2



)






CONSISTENCY AND ASYMPTOTIC NORMALITY OF STOCHASTIC EULER SCHEMES FOR ORDINARY DIFFERENTIAL EQUATIONS 7

≤ const ∆

N

2N
X
k=1

E

"

N

sup x̂ (t) − x(t)

t∈[0,T ]

2

#

→ 0 as N → ∞.

(4.8)

By (4.8) the summed first error terms converge to zero in probability. The sum involving the error terms
 − 1 P


R tN
N
N
R3N,k is deterministic and converges to zero: We have ∆N 2 k:0<tkN ≤t tNk F tk−1
, xk−1
− F(s, x(s)) ds ≤
k−1
  12
const ∆N . Finally, consider the sum involving the second error terms R2N,k :
Y 
X

   1 n 





o
N
N
N
N
N
N
N
N
I + ∆N ∇ x F tNj−1 , xNj−1 ∆N 2 F tk−1
, x̂k−1
− F tk−1
, xk−1
− ∇ x F tk−1
, xk−1
x̂k−1
− xk−1
.
k:0<tkN ≤t j:tkN <t Nj ≤t

(4.9)
ξiN,k−1

N
N
We apply the mean value theorem to each component Fi of F and get for suitable
between x̂k−1
and xk−1
for the norm of equation (4.9) the bound
v
u
t d
X
X

 2


  21
N
N
N
N
N
, xk−1
, ξiN,k−1 − ∇ x Fi tk−1
∇ x Fi tk−1
≤ ∆
exp (T k∇ x F( · , x( · ))k∞ ) sup x̂ (t) − x(t)
t∈[0,T ]

0<tkN ≤t

X
 1
≤ ∆N 2 exp (T k∇ x F( · , x( · ))k∞ ) sup x̂N (t) − x(t)
t∈[0,T ]

i=1

d
X

0<tkN ≤t i=1





N
N
N
, xk−1
, ξiN,k−1 − ∇ x Fi tk−1
∇ x Fi tk−1
(4.10)

Next, define the sets Aρ := {y ∈ Rd : ky − x(t)k ≤ ρ for some t ∈ [0, T ]}. Then the functions ∇ x Fi are uniformly
continuous on [0, T ] × A1 . Hence, for every ε > 0 there is a δ > 0 such that for all (t, x), (s, y) ∈ [0, T ] × A1
with k(t, x) − (s, y)k < δ, we have maxi=1,...,d k∇ x Fi (t, x) − ∇ x Fi (s, y)k < ε. Furthermore, due to the Lipschitzcontinuity of F all gradients ∇ x Fi are bounded. Consequently, we obtain for the terms in the sum of equation
(4.10) that




N
N
N
, xk−1
≤ K4 1{sup{k x̂N (t)−x(t)k :t∈[0,T ]}>δ} + ε1{sup{k x̂N (t)−x(t)k :t∈[0,T ]}≤δ}
, ξiN,k−1 − ∇ x Fi tk−1
∇ x Fi tk−1
for a suitable constant 0 < K4 < ∞. This proves that the expectation of (4.10) can be made arbitrarily small
depending on the choice of ε > 0 as N converges to infinity. Thus, the summed third error converges to
zero in distribution. Hence, the overall error converges in distribution to the constant zero. Theorem 2.7 of
Van Der Vaart [1998] states that for random variables Xn and Yn such that Xn ⇒ X and Yn ⇒ c where c is a
constant, we have (Xn , Yn ) ⇒ (X, c). This yields the desired asymptotic normality.

Appendix A. Deferred Proofs and Background Material
Lemma A.1 (Discrete Gronwall Inequality). Let { fk : k ∈ N}, {gk : k ∈ N}, {yk : k ∈ N} be positive sequences
Pn−1
Qn−1
P
in R≥0 which fulfill yn ≤ fn + n−1
j=k+1 (1 + g j ) ≤
k=0 gk yk for every n ∈ N. Then, we have yn ≤ fn + k=0 fk gk


Pn−1
Pn−1
fn + k=0 fk gk exp j=k+1 g j for each n ∈ N. The first inequality is actually sharp.
Lemma A.2 (Estimates for characteristic functions). Let X be a d-dimensional real random variable on
(Ω, A, P) and let G ⊆ A be a sub-σ-algebra of A. Define µ = E [ X | G ] and Σ := E [ XX ′ | G ]. Then
for the conditional characteristic function of X w.r.t. G, ϕX |G , it holds that for each t ∈ Rd
!
h
i
1
iht,Xi
ϕX |G (t) = E e
G = 1 − ht, Σti eiht,µi + r(t),
2
where the remainder can be bounded as follows
h
i
h
i
|r(t)| ≤ 2 ktk2 E kXk2 1{ktk kXk>ε/2} | G + ε ktk2 E kXk2 1{ktk kXk≤ε} | G .
Proof. We can decompose the conditional characteristic function in a real and an imaginary function
ϕX|G (t) = E [ cosht, Xi | G ] + i E [ sinht, Xi | G ]

from which we can compute the gradients and the Hessian matrices. We get for the gradient of the sin- and
cos-term
t 7→ −E [ sinht, Xi · X | G ] and t 7→ E [ cosht, Xi · X | G ] .
The Hessian matrices are given by




t 7→ −E X · cosht, Xi · X ′ and by t 7→ −E X · sinht, Xi · X ′ .

8

JOHANNES T. N. KREBS

In the first place let E [ X | G ] = 0 a.s.[P], then

E [ cosht, Xi | G ] = 1 − 21 · t′ · E  X · X ′ | G  · t − 12 · t′ · E  X · (coshθ1 t, Xi − 1) · X ′ | G  · t,
E [ sinht, Xi | G ] = − 12 · t′ · E  X · sinhθ2 t, Xi · X ′ | G  · t,

for suitable θ1 , θ2 ∈ [0, 1] by the mean value theorem. Hence, ϕX|G (t) = 1 − 12 ht, Σti + r(t), where


i

o E
1 D n h
|r(t)| =
t, E X · coshθ1 t, Xi − 1 · X ′ | G + iE X · sinhθ2 t, Xi · X ′ | G t
2
h


i E
D
1
≤
sup t, E X · exp(ihθ1 t, Xi) − 1 · X ′ | G t
2 θ1 ∈[0,1]
D
h


i E
1
+
t, E X · sinhθ2 t, Xi − sinhθ1 t, Xi · X ′ | G t
sup
2 θ1 ,θ2 ∈[0,1]
Next, we make use of the estimate |1 − eiα | ≤ min{|α|, 2} real α for the first term. For the second term, we
use that the real sinus function is Lipschitz continuous with Lipschitz-constant 1, i.e. | sin x − sin y| ≤ |x − y|.
Hence, we have the following two estimates,
h


i E
h
i
D
t, E X · exp(ihθ1 t, Xi) − 1 · X ′ | G t ≤ ktk2 E kXk2 | exp(i hθ1 t, Xi) − 1| | G
h
i
h
i
≤ 2 ktk2 E kXk2 1{ktk kXk>ε} | G + ε ktk2 E kXk2 1{ktk kXk≤ε} | G .
And,

D

h


i E
t, E X · sinhθ2 t, Xi − sinhθ1 t, Xi · X ′ | G t
h
i
h
i
≤ 2 ktk2 E kXk2 1{ktk kXk>ε/2} | G + ε ktk2 E kXk2 1{ktk kXk≤ε/2} | G .

Combining these estimates, the remainder can be bounded as claimed. For general µ, we find that ϕX|G (t) =
ϕX−µ (t)eiht,µi , hence, we can apply the above analysis once again. This finishes the proof.

Lemma A.3. Let πN , N ∈ N+ , be the sequence of dyadic partitions of [0, T ], T > 0, such that 0 = τ0N < τ1N <
... < τ2NN = T . Let χ be a continuous matrix valued mapping from [0, T ] to Rd×d . Let || · || be a submultiplicative
matrix norm on Rd×d . Then there is a continuous map
P : [0, T ]2 → Rd×d such that

sup

Y 

s,t∈[0,T ],
s<tiN ≤t
s≤t

 
N
I + ∆iN χ ti−1
− P(s, t) → 0 as N → ∞.


 
Q
N
Proof. For 0 ≤ s ≤ t ≤ T write PN (s, t) := s<tiN ≤t I + ∆iN χ ti−1
. We show that the (PN )N∈N+ are Cauchy
N
N
w.r.t. k · k∞ on [0, T ]. Fix some
 0≤ s ≤ t ≤ T . Let M ≥ N. Then for a k ≤ 2 , we have P (s, t) = D0 ·D1 ·. . .·Dk ,
N
N
N
where each Di = I + ∆i χ ti−1 for some ti ∈ (s, t] and D0 is determined by the unique tlN which fulfills
N
tl−1
≤ s < tlN ≤ t . Since πN ⊆ π M , we can choose for i = 1, . . . , k the factors
i
i

i 





 
M
M
M
N
M
M
M
, tu+v
, tuM ∪ . . . ∪ tu+v−1
such that for i , l : ti−1
, tiN = tu−1
· . . . · I + ∆u+v
χ tu+v−1
Fi = I + ∆uM χ tu−1
for v = 2 M−N − 1. Furthermore, there is a factor F0 given by

 



M
M
M
F0 = I + ∆lM χ tl−1
· . . . · I + ∆l+ṽ
χ tl+ṽ−1

M
for the unique tlM which fulfills tl−1
≤ s < tlM ≤ t and ṽ ≤ 2 M−N . Then P M (s, t) = F0 · F1 · . . . · Fk · Res, where
M
the residual factors of P (s, t) are collected in Res. Hence, we can write

P M (s, t) − PN (s, t) = F0 · F1 · . . . · Fk · Res − D0 · D1 · . . . · Dk

= (F0 − I) · F1 · . . . · Fk · Res + F1 · . . . · Fk · (Res − I)

(A.1)
+ F1 · . . . · Fk − D1 · . . . · Dk − (D0 − I) · D1 · . . . · Dk .




Firstly, we have kResk ≤ exp ∆N kχk∞ , as well as, max kF1 ·, . . . · Fk k , kD1 ·, . . . · Dk k ≤ exp T kχk∞ and
secondly,



max kF0 − Ik , kD0 − Ik , kRes − Ik ≤ ∆N kχk∞ exp ∆N kχk∞ .

CONSISTENCY AND ASYMPTOTIC NORMALITY OF STOCHASTIC EULER SCHEMES FOR ORDINARY DIFFERENTIAL EQUATIONS 9

Thirdly, we can write the main term as F1 ·. . .·Fk −D1 ·. . .·Dk =
which implies for the norm of this term
kF1 · . . . · Fk − D1 · . . . · Dk k ≤

k
X
j=1

Pk

j=1

Qj

i=1

Fi

Qk

i= j+1

Di −

Pk−1 Q j
j=0

max kFi k j−1 F j − D j max kDi kk− j .

1≤i≤k

1≤i≤k

i=1

Fi

Qk

i= j+1

Di ,

(A.2)

The factors of each summand in (A.2) can be estimated as follows, we have for the first and the third factor




M−N
kDi k ≤ 1 + ∆N kχk∞ ≤ exp ∆N kχk∞ as well as kFi k ≤ (1 + ∆ M kχk∞ )2
≤ exp ∆N kχk∞ .

For the factor in the middle, we use the definition of the modulus of continuity: Define for δ > 0 the function
w(δ, χ) := sup{||χ(s) − χ(t)|| : |s − t| ≤ δ}. Then
M−N
!
2X
j
 2


2 M−N  M
N
N
F j − D j ≤ ∆ w(∆ , χ) +
∆ kχk∞ ≤ ∆N w(∆N , χ) + ∆N kχk2∞ exp ∆N kχk∞ .
j
j=2


Eventually, we combine these estimates to find that (A.1) can be bounded over all s and t by c ∆N + w(∆N , χ) ,
for a suitable constant 0 < c < ∞ which does not depend on N. Since χ is uniformly continuous on [0, T ],
we have limN→∞ w(∆N , χ) = 0. This proves the Cauchy property and consequently the uniform convergence
of the sequence (PN )N∈N+ to a limit function P. It remains to prove the continuity of this P. We have for all
(s, t), (s0 , t0 ) in [0, T ]2 that
kP(s, t) − P(s0 , t0 )k ≤ P(s, t) − PN (s, t) + PN (s, t) − PN (s0 , t)

+ PN (s0 , t) − PN (s0 , t0 ) + PN (s0 , t0 ) − P(s0 , t0 ) .

(A.3)

And we can compute, that for 0 ≤ a < b < c ≤ T , we have
Y 

a<tiN ≤b

  Y 
 





I + ∆N χ tiN −
I + ∆N χ tiN
≤ kχk∞ exp T kχk∞ exp (c − b + ∆N ) kχk∞ (c − b) + ∆N
a<tiN ≤c

where the terms involving the ∆N stem from the fact that PN is discontinuous at the partitioning points. All in
all, the remaining terms in equation (A.3) can be bounded with

n
o

max PN (s, t) − PN (s0 , t) , PN (s0 , t) − PN (s0 , t0 ) ≤ const | max(|s − s0 |, |t − t0 |) + ∆N

This yields the desired continuity of the limit function P.



References
Marco Chiani, Davide Dardari, and Marvin K Simon. New exponential bounds and approximations for the
computation of error probability in fading channels. Wireless Communications, IEEE Transactions on, 2
(4):840–845, 2003.
Raúl Fierro and Soledad Torres. The euler scheme for hilbert space valued stochastic differential equations.
Statistics & probability letters, 51(3):207–213, 2001.
Raul Fierro and Soledad Torres. A stochastic scheme of approximation for ordinary differential equations.
Electronic Communications in Probability, 13:1–9, 2007.
A.W. Van Der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics, 3.
Cambridge University Press, 1998. ISBN 9780521496032.
E-mail address: krebs@mathematik.uni-kl.de
University of Kaiserslautern, Erwin-Schrödinger-Strasse, 67663 Kaiserslautern

