# Properties of the Euler Discretization of a diffusion

Let $X$ be a continuous 1-d diffusion:

$$dX_t = a(X_t)dt + b(X_t)dW_t, X_0 = x.$$ W is a standard Brownian Motion and $a(\cdot)$ and $b(\cdot)$ can have nice regularity properties.

Let $Z^n_1,Z^n_2,\ldots$ be i.i.d. standard normal random variables. The Euler discretization $X^n$ with step size $\frac{1}{n}$ is the process given by

$$X^n_\frac{k}{n} = X^n_\frac{k-1}{n} + \frac{1}{n}\cdot a(X^n_\frac{k-1}{n}) + \frac{1}{\sqrt{n}}b(X^n_\frac{k-1}{n}) \cdot Z^n_k, X^n_0 = x.$$

A (at least to me) reasonable way to embed $X$ and $X^1,X^2,\ldots$ on the same probability space is by taking the $Z_i$ generated by the increments of the Brownian Motion $W$: $Z^n_i = \sqrt{n} \cdot (W_\frac{i}{n} - W_\frac{i-1}{n})$.

The reason why I want all process defined on the same space is that I want convergence rates, and I have heard that weak convergence results aren't appropriate for this, although I don't really understand why.

It's believable that in some sense $X^n \rightarrow X$. There are several different types of convergence available (expectation over product space, expectation of time supremum). I'm interested in what kind of convergence there is, and specifically in the convergence rates.

Motivation: the problem I'm studying is an optimal stopping problem on a diffusion when there is perfect information. When information comes at discrete times, it becomes a weird discretization, which can be approximated by the one above. I'd like to see how fast there is convergence to the perfect information case.

-

Given your interest in optimal stopping, the relevant result for you is probably strong uniform convergence, by which I mean convergence of the expectation of the time supremum. If your coefficients $a$ and $b$ are Lipschitz, then I believe the result is well-known. The proof is simple with the right "embedding", as you mentioned. Without more information about how stopping times come in to your particular problem, it's hard to know if this is a useful suggestion, but here is the idea anyway:

Suppose there exists $L > 0$ such that $|a(x) - a(y)| + |b(x) - b(y)| \le L|x-y|$. Fix a time horizon $T > 0$. Define $t^n_j = jT/n$ for $j=0,\ldots,n$. For trajectories $x$ and times $t$ define $\lfloor t \rfloor _ n := \max\{t^n_j : t^n_j\le t, \ j=0,\ldots,n\}$ and $a^n(t,x) := a(x(\lfloor t \rfloor _ n))$. Define $b^n$ similarly. Let $X^n$ solve the SDE $dX^n_t = a^n(t,X^n)dt + b^n(t,X^n)dW_t$, $X^n_0 = x$. This is trivially solveable, just by noting that the SDE is actually equivalent to the following recursion:

$X^n(t) = X^n(t^n_{j}) + a(X^n(t^n_{j}))(t - t^n_j) + b(X^n(t^n_{j}))(W(t) - W(t^n_j))$, for $t \in [t^n_j,t^n_{j+1}]$.

This is your desired embedding, and it is straightforward to prove with Doob's and Gronwall's inequalities that

$\mathbb{E}[\sup_{0 \le t \le T}|X(t) - X^n(t)|^2] \rightarrow 0$.

-
Thanks, this is the convergence that I was most interested in. Do you have a reference for this fact, and is the convergence rate $O(t)$? –  weakstar Nov 19 '12 at 0:51
Also, do you know any general references about convergence properties for optimal stopping problems? For example, the above kind of uniform convergence is something I need, but by itself does not imply convergence of optimal stopping, since i.e. hitting times aren't continuous with respect to the uniform norm. –  weakstar Nov 19 '12 at 2:05
I can't seem to find a reference for this type of convergence, except in some non-Lipschitz cases. Maybe you can chase their references: hal.inria.fr/docs/00/05/42/25/PDF/RR-5637-V2.pdf and arxiv.org/pdf/1010.3756.pdf The rate should be at least $n^{-1/2}$. When you say "convergence of optimal stopping", what do you mean exactly? Convergence of the value function, or convergence of the optimal time itself? Such a question may warrant a new post. –  Dan Nov 19 '12 at 14:41

What you call the Euler discretization is sometimes called the Euler-Maruyama discretization. There is a lot of literature about its convergence properties. One place to look is the classic book by Kloeden and Platen (Numerical Solution of Stochastic Differential Equations). Another is Milstein and Tretyakov (Stochastic Numerics for Mathematical Physics). A very convenient and readable introduction is the paper by Des Higham http://epubs.siam.org/doi/pdf/10.1137/S0036144500378302.

-
Thanks for your answer. It seems like strong convergence doesn't have much to say about convergence of optimal stopping problems, unless you can leverage some additional information, like martingality, to use a maximal inequality. Kloeden/Platen also don't have anything to say about this. Do you know of anything in this direction? –  weakstar Nov 17 '12 at 22:59
I see that Dan has already answered this, but the proof of convergence in the sup norm is in Theorem 9.6.2 of the 1st edition of Kloeden and Platen. –  Paul Tupper Nov 19 '12 at 19:20
Also, I'm not sure what you're looking for, but Chapter 5 of Milstein and Tretyakov is "Simulation of space and space-time bounded diffusions". Subsection 5.4.3 is "Approximation of exit point" for SDEs. –  Paul Tupper Nov 19 '12 at 19:24