Numerical Solution of Stochastic Differential Equations

Abstract

Stochastic differential equations (SDEs) including the geometric Brownian motion are widely used in natural sciences and engineering. In finance they are used to model movements of risky asset prices and interest rates. The solutions of SDEs are of a different character compared with the solutions of classical ordinary and partial differential equations in the sense that the solutions of SDEs are stochastic processes. Thus it is a nontrivial matter to measure the efficiency of a given algorithm for finding numerical solutions.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Stochastic differential equations (SDEs) including the geometric Brownian motion are widely used in natural sciences and engineering. In finance they are used to model movements of risky asset prices and interest rates. The solutions of SDEs are of a different character compared with the solutions of classical ordinary and partial differential equations in the sense that the solutions of SDEs are stochastic processes. Thus it is a nontrivial matter to measure the efficiency of a given algorithm for finding numerical solutions. In this chapter we introduce two methods for numerically solving stochastic differential equations. For more details consult [50, 92].

1 Discretization of Stochastic Differential Equations

Given an SDE

$$\displaystyle{\mathrm{d}X_{t} = a(t,X_{t})\,\mathrm{d}t + b(t,X_{t})\,\mathrm{d}W_{t}\;,\quad X_{0} = x_{0}}$$

defined on a time interval [t ₀, T], we consider its corresponding time discretization

$$\displaystyle{Y _{n+1} = Y _{n} + a(t_{n},Y _{n})\,\varDelta _{n} + b(t_{n},Y _{n})\,\varDelta W_{n}\;,\quad n = 0,1,\cdots \,,N - 1}$$

where t ₀ < t ₁ < ⋯ < t _N  = T, $\varDelta _{n} = t_{n+1} - t_{n}$, $\varDelta W_{n} = W_{t_{n+1}} - W_{t_{n}}$, and study iterative algorithms to find numerical solutions.

To plot a sample path for Y _t on an interval t ∈ [t ₀, T] we plot a piecewise linear function defined by

$$\displaystyle{Y _{t} = Y _{t_{n}} + \frac{t - t_{n}} {t_{n+1} - t_{n}}(Y _{t_{n+1}} - Y _{t_{n}})\;,\quad t_{n} \leq t \leq t_{n+1}\;,}$$

which reflects the nondifferentiability of a sample path of X _t  .

Definition 30.1 (Strong Convergence)

Let $\delta =\max _{n}\vert t_{n+1} - t_{n}\vert$. Suppose that an SDE for X _t has a discrete solution Y _n such that there exists δ ₀ > 0, γ > 0 and K > 0 for which

$$\displaystyle{\mathbb{E}[\vert X_{T} - Y _{N}\vert ] \leq K\delta ^{\gamma }\quad \text{for every }0 <\delta <\delta _{0}\;.}$$

Then we say that Y converges to X in the strong sense and call γ the order of strong convergence.

Definition 30.2 (Weak Convergence)

Let $\delta =\max _{n}\vert t_{n+1} - t_{n}\vert$. Suppose that an SDE for X _t has a discrete solution Y _n such that there exists δ ₀ > 0, β > 0 and K > 0 for which

$$\displaystyle{\vert \mathbb{E}[g(X_{T})] - \mathbb{E}[g(Y _{N})]\vert \leq K\delta ^{\beta }\quad \text{for every }0 <\delta <\delta _{0}}$$

for an arbitrary nice function g such as a polynomial or a piecewise linear function. Then we say that Y converges to X in the weak sense and call β the order of weak convergence.

Remark 30.1

• (i) If we take g(x) = x and $g(x) = (x - \mathbb{E}[X_{T}])^{2}$ in the previous definition of weak convergence, we can obtain the average and variance of X _T , respectively.

• (ii) Let ϕ(x) be a convex function. Then, by Jensen’s inequality we have $\mathbb{E}[\phi (X)] \geq \phi (\mathbb{E}[X])$. If we take ϕ(x) =  | x | , then we obtain

  $$\displaystyle{\mathbb{E}[\vert X_{T} - Y _{N}\vert ] \geq \vert \mathbb{E}[X_{T} - Y _{N}]\vert = \vert \mathbb{E}[X_{T}] - \mathbb{E}[Y _{N}]\vert \;.}$$

• (iii) In many applications we need not find the values of X _t for all 0 ≤ t ≤ T. For example, to compute the price of a European option where C _T denotes the payoff function at maturity T it suffices to know C _T (X _T ). That is, it is enough to consider the weak convergence speed.

• (iv) Since the root mean square of Δ W _n is not δ but δ ^1∕2, the discrete approximate solution of an SDE has a smaller order of convergence than the discrete approximate solution of an ordinary differential equation, in general.

• (v) Consider a computer simulation for strong convergence where t ₀ = 0. We take the time step $\delta = \frac{T} {N}$, and obtain a discrete solution Y and its values at T, denoted by Y _T ^j, 1 ≤ j ≤ J, and compute

  $$\displaystyle{\varepsilon (\delta ) = \frac{1} {J}\sum _{j=1}^{J}\vert X_{ T}^{j} - Y _{ N}^{j}\vert }$$

  and finally plot the graph of $-\log \varepsilon (\delta )$ against $-\log \delta$ for the values $\delta = 2^{-3},2^{-4},2^{-5}$, and so on.

From now on we treat only the case when the functions a and b do not depend on t.

2 Stochastic Taylor Series

In this section we present the Taylor series expansion of a stochastic process given by an SDE $\mathrm{d}X_{t} = a(t,X_{t})\mathrm{d}t + b(t,X_{t})\mathrm{d}W_{t}$. If a(t, x) = a(t) and b(t, x) = 0, then we have the usual Taylor series expansion. In the following discussion, for the sake of notational simplicity, we consider the case when a(t, x) and b(t, x) are functions of x only.

2.1 Taylor Series for an Ordinary Differential Equation

Given a sufficiently smooth function $a(x): \mathbb{R} \rightarrow \mathbb{R}$, we consider a one-dimensional autonomous ordinary differential equation $\frac{\mathrm{d}} {\mathrm{d}t}X_{t} = a(X_{t})$ on the time interval [t ₀, T] which has a solution X _t with an initial data $X_{t_{0}}$. We may rewrite the equation as

$$\displaystyle{ X_{t} = X_{t_{0}} +\int _{ t_{0}}^{t}a(X_{ s})\,\mathrm{d}s\;. }$$

(30.1)

Given a C ¹ function $f: \mathbb{R} \rightarrow \mathbb{R}$, we have

$$\displaystyle{ \frac{\mathrm{d}} {\mathrm{d}t}\left (f(X_{t})\right ) = f'(X_{t}) \frac{\mathrm{d}} {\mathrm{d}t}X_{t} = a(X_{t}) \frac{\partial } {\partial x}f(X_{t})}$$

by the chain rule. If we let L be a differential operator defined by

$$\displaystyle{ L = a(x) \frac{\partial } {\partial x}\;, }$$

then

$$\displaystyle{ \frac{\mathrm{d}} {\mathrm{d}t}\left (\,f(X_{t})\right ) = Lf(X_{t})\;.}$$

Equivalently,

$$\displaystyle{ f(X_{t}) = f(X_{t_{0}}) +\int _{ t_{0}}^{t}L\,f(X_{ s})\,\mathrm{d}s\;. }$$

(30.2)

If we substitute f(x) = a(x) in (30.2), then we obtain

$$\displaystyle{ a(X_{t}) = a(X_{t_{0}}) +\int _{ t_{0}}^{t}L\,a(X_{ s})\,\mathrm{d}s\;. }$$

(30.3)

Substituting (30.3) back into (30.1), we have

$$\displaystyle\begin{array}{rcl} X_{t}& =& X_{t_{0}} +\int _{ t_{0}}^{t}\left (a(X_{ t_{0}}) +\int _{ t_{0}}^{s}La(X_{ z})\mathrm{d}z\right )\mathrm{d}s \\ & =& X_{t_{0}} + a(X_{t_{0}})\,(t - t_{0}) +\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}La(X_{ z})\,\mathrm{d}z\,\mathrm{d}s\;.{}\end{array}$$

(30.4)

Similarly, if we substitute f = La in (30.2) then we obtain

$$\displaystyle{ La(X_{t}) = La(X_{t_{0}}) +\int _{ t_{0}}^{t}L^{2}a(X_{ u})\,\mathrm{d}u\;, }$$

(30.5)

and, by substituting (30.5) back into (30.4), we obtain

$$\displaystyle\begin{array}{rcl} X_{t}& =& X_{t_{0}} + a(X_{t_{0}})\int _{t_{0}}^{t}\mathrm{d}s +\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}\left (La(X_{ t_{0}}) +\int _{ t_{0}}^{z}L^{2}a(X_{ u})\mathrm{d}u\right )\mathrm{d}z\,\mathrm{d}s \\ & =& X_{t_{0}} + a(X_{t_{0}})\,(t - t_{0}) + \frac{1} {2}La(X_{t_{0}})\,(t - t_{0})^{2} + R(t_{ 0};t)\;, {}\end{array}$$

(30.6)

where

$$\displaystyle{R(t_{0};t) =\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}\int _{ t_{0}}^{z}L^{2}a(X_{ u})\,\mathrm{d}u\,\mathrm{d}z\,\mathrm{d}s\;.}$$

The idea is to keep on substituting the nth order approximation of X _t into the original equation (30.1) to obtain the (n + 1)-st order approximation.

2.2 Taylor Series for a Stochastic Differential Equation

Now we consider the Taylor series expansion for an SDE

$$\displaystyle{ \mathrm{d}X_{t} = a(X_{t})\,\mathrm{d}t + b(X_{t})\,\mathrm{d}W_{t}\;. }$$

(30.7)

By Itô’s lemma, we have

$$\displaystyle\begin{array}{rcl} f(X_{t})& =& f(X_{t_{0}}) +\int _{ t_{0}}^{t}\left (a(X_{ s})\frac{\partial f} {\partial x}(X_{s}) + \frac{1} {2}b^{2}(X_{ s})\frac{\partial ^{2}f} {\partial x^{2}}(X_{s})\right )\mathrm{d}s \\ & & +\int _{t_{0}}^{t}b(X_{ s})\frac{\partial f} {\partial x}(X_{s})\,\mathrm{d}W_{s} \\ & =& f(X_{t_{0}}) +\int _{ t_{0}}^{t}L^{0}f(X_{ s})\,\mathrm{d}s +\int _{ t_{0}}^{t}L^{1}f(X_{ s})\,\mathrm{d}W_{s} {}\end{array}$$

(30.8)

where

$$\displaystyle{L^{0} = a \frac{\partial } {\partial x} + \frac{1} {2}b^{2} \frac{\partial ^{2}} {\partial x^{2}}\;,\quad L^{1} = b \frac{\partial } {\partial x}\;.}$$

If we take f(x) = x in (30.8), we have

$$\displaystyle{L^{0}f = a\;,\quad L^{1}f = b}$$

and recover the original equation (30.7) rewritten in the integral form as

$$\displaystyle{ X_{t} = X_{t_{0}} +\int _{ t_{0}}^{t}a(X_{ s})\,\mathrm{d}s +\int _{ t_{0}}^{t}b(X_{ s})\,\mathrm{d}W_{s}\;. }$$

(30.9)

We take

$$\displaystyle{f = a\;,\quad f = b}$$

in (30.8) and obtain

$$\displaystyle{ a(X_{t}) = a(X_{t_{0}}) +\int _{ t_{0}}^{t}L^{0}a(X_{ s})\,\mathrm{d}s +\int _{ t_{0}}^{t}L^{1}a(X_{ s})\,\mathrm{d}W_{s} }$$

(30.10)

and

$$\displaystyle{ b(X_{t}) = b(X_{t_{0}}) +\int _{ t_{0}}^{t}L^{0}b(X_{ s})\,\mathrm{d}s +\int _{ t_{0}}^{t}L^{1}b(X_{ s})\,\mathrm{d}W_{s}\;. }$$

(30.11)

We substitute (30.10) and (30.11) into (30.9), and obtain

$$\displaystyle\begin{array}{rcl} X_{t}& =& X_{t_{0}} +\int _{ t_{0}}^{t}\left (a(X_{ t_{0}}) +\int _{ t_{0}}^{s}L^{0}a(X_{ u})\,\mathrm{d}u +\int _{ t_{0}}^{s}L^{1}a(X_{ u})\,\mathrm{d}W_{u}\right )\mathrm{d}s \\ & & +\int _{ t_{0}}^{t}\left (b(X_{ t_{0}}) +\int _{ t_{0}}^{s}L^{0}b(X_{ u})\,\mathrm{d}u +\int _{ t_{0}}^{s}L^{1}b(X_{ u})\,\mathrm{d}W_{u}\right )\mathrm{d}W_{s} \\ & =& X_{t_{0}} + a(X_{t_{0}})\,(t - t_{0}) + b(X_{t_{0}})\,(W_{t} - W_{t_{0}}) + R(t_{0};t){}\end{array}$$

(30.12)

where

$$\displaystyle\begin{array}{rcl} R(t_{0};t)& =& \int _{t_{0}}^{t}\int _{ t_{0}}^{s}L^{0}a(X_{ u})\,\mathrm{d}u\,\mathrm{d}s +\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}L^{1}a(X_{ u})\,\mathrm{d}W_{u}\,\mathrm{d}s {}\\ & & +\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}L^{0}b(X_{ u})\,\mathrm{d}u\,\mathrm{d}W_{s} +\int _{ t_{0}}^{t}\int _{ t_{0}}^{s}L^{1}b(X_{ u})\,\mathrm{d}W_{u}\,\mathrm{d}W_{s}\;. {}\\ \end{array}$$

From (30.8) we have

$$\displaystyle\begin{array}{rcl} f(X_{t})& =& f(X_{t_{0}}) + L^{0}f(X_{ t_{0}})\int _{t_{0}}^{t}\mathrm{d}s + L^{1}f(X_{ t_{0}})\int _{t_{0}}^{t}\mathrm{d}W_{ s} {}\\ & & + c(X_{t_{0}})\int _{t_{0}}^{t}\int _{ t_{0}}^{s_{2} }\mathrm{d}W_{s_{1}}\mathrm{d}W_{s_{2}} + R(\,f,t_{0};t) {}\\ \end{array}$$

where

$$\displaystyle{ c(x) = b(x)\left \{b(x)f''(x) + b'(x)f'(x)\right \}\;. }$$

(30.13)

Note that

$$\displaystyle\begin{array}{rcl} \int _{t_{0}}^{t}\int _{ t_{0}}^{s_{2} }\mathrm{d}W_{s_{1}}\mathrm{d}W_{s_{2}}& =& \int _{t_{0}}^{t}(W_{ s_{2}} - W_{t_{0}})\,\mathrm{d}W_{s_{2}} {}\\ & =& \int _{t_{0}}^{t}W_{ s_{2}}\,\mathrm{d}W_{s_{2}} - W_{t_{0}}\int _{t_{0}}^{t}\mathrm{d}W_{ s_{2}} {}\\ & =& \frac{1} {2}\{W_{t}^{2} - W_{ t_{0}}^{2} - (t - t_{ 0})\} - W_{t_{0}}(W_{t} - W_{t_{0}}) {}\\ & =& \frac{1} {2}\{(W_{t} - W_{t_{0}})^{2} - (t - t_{ 0})\}\;. {}\\ \end{array}$$

Hence (30.13) becomes

$$\displaystyle\begin{array}{rcl} f(X_{t})& =& f(X_{t_{0}}) + L^{0}f(X_{ t_{0}})(t - t_{0}) + L^{1}f(X_{ t_{0}})(W_{t} - W_{t_{0}}) \\ & & +\frac{1} {2}c(X_{t_{0}})\{(W_{t} - W_{t_{0}})^{2} - (t - t_{ 0})\} + R(\,f,t_{0};t)\;.{}\end{array}$$

(30.14)

If we take f(x) = x in (30.14), then

$$\displaystyle\begin{array}{rcl} X_{t}& =& X_{t_{0}} + a(X_{t_{0}})\,(t - t_{0}) + b(X_{t_{0}})\,(W_{t} - W_{t_{0}}) \\ & & +\frac{1} {2}b(X_{t_{0}})b'(X_{t_{0}})\{(W_{t} - W_{t_{0}})^{2} - (t - t_{ 0})\} + R(\,f,t_{0};t).{}\end{array}$$

(30.15)

3 The Euler Scheme

Consider an SDE

$$\displaystyle{\mathrm{d}X_{t} = a(X_{t})\,\mathrm{d}t + b(X_{t})\,\mathrm{d}W_{t}\;,\quad X_{0} = x_{0}}$$

defined on the time interval [t ₀, T]. Here, for the sake of notational simplicity, we consider the case when a(t, x) and b(t, x) are functions of x only. The Euler scheme is a numerical method based on the approximation given by (30.12), after truncation of the remainder term R(t ₀; t), to find a numerical solution of

$$\displaystyle{Y _{n+1} = Y _{n} + a(Y _{n})\varDelta _{n} + b(Y _{n})\varDelta W_{n}\;,\quad n = 0,1,\ldots,N - 1}$$

at $0 = t_{0} < t_{1} < \cdots < t_{N} = T$, where Y ₀ = x ₀, $\varDelta _{n} = t_{n+1} - t_{n}$, $\varDelta W_{n} = W_{t_{n+1}} - W_{t_{n}}$. The increment Δ W _n has normal distribution with average 0 and variance Δ _n . The increments Δ W _n are independent of each other and obtained by random number generators in computer simulations.

If a and b are bounded and Lipschitz continuous, then the Euler scheme has strong order γ = 0. 5. On the other hand, the strong order of a discretized numerical solution of an ordinary differential equation is equal to 1. The weak order of the Euler scheme is equal to β = 1.

In Fig. 30.1 is plotted the speed of numerical approximation by the Euler scheme for geometric Brownian motion

$$\displaystyle{\mathrm{d}S_{t} =\mu \, S_{t}\,\mathrm{d}t +\sigma \, S_{t}\,\mathrm{d}W_{t}}$$

with μ = 0. 5, $\sigma = 0.6$. The points $(n,-\log \varepsilon _{n})$, 4 ≤ n ≤ 10, are plotted. In this case, since we have a closed form solution, we can compare the numerical solution obtained by the Euler scheme with the theoretical solution, where we take time step $\delta = 2^{-n}$, 4 ≤ n ≤ 10, and sample size 10⁴.

Fig. 30.1

The Euler Scheme: speeds of strong convergence (left) and weak convergence (right)

In the case of strong convergence the error satisfies $\varepsilon \approx K\delta ^{\gamma }$, and hence we have

$$\displaystyle{-\log _{2}\varepsilon \approx -\log _{2}K +\gamma \, n\;.}$$

Thus the slope of the regression line is approximately equal to γ if we plot $-\log _{2}\varepsilon$ for each n. In the case of weak convergence the slope is approximately equal to β. In Fig. 30.1 we observe that the slope in the first graph is close to 0. 5 and in the second graph the slope is approximately equal to 1, and thus the speed of convergence to zero is exponential.

4 The Milstein Scheme

The Milstein scheme is a numerical method based on the approximation given by (30.15), after truncation of the remainder term R( f, t ₀; t), to find a numerical solution of

$$\displaystyle{Y _{n+1} = Y _{n} + a(Y _{n})\varDelta _{n} + b(Y _{n})\varDelta W_{n} + \frac{1} {2}b(Y _{n})\,b'(Y _{n})\left \{(\varDelta W_{n})^{2} -\varDelta _{ n}\right \}}$$

for $n = 0,1,\ldots,N - 1$ at $0 = t_{0} < t_{1} < \cdots < t_{N} = T$, where b′(x) denotes the derivative of b(x) with respect to x. It was named after Grigori N. Milstein [69].

If $\mathbb{E}[(X_{0})^{2}] < \infty$ and if a and b are twice continuously differentiable and the second order derivatives are Lipschitz continuous, then the order of strong convergence of the Milstein scheme is γ = 1. 0. The order of weak convergence is also β = 1. 0.

Figure 30.2 displays numerical results from the Milstein scheme for geometric Brownian motion with μ = 0. 5, $\sigma = 0.6$. The sample size is 10⁴. Observe that the slopes are approximately equal to 1 in both cases.

Fig. 30.2

The Milstein Scheme: speeds of strong convergence (left) and weak convergence (right)

5 Computer Experiments

Simulation 30.1 (Euler Scheme: Weak Convergence)

We test the speed of weak convergence of the Euler scheme for solving the geometric Brownian motion when we take $g(x) = (x - \mathbb{E}[X_{T}])^{2}$.

T = 1;

N = [2^4,2^5,2^6,2^7,2^8,2^9,2^10];

J = 10^4;

mu = 0.5;

sigma = 0.6;

X_0 = 10;

X_T=zeros(1,J);

Y_N=zeros(1,J);

for n=1:length(N)

    dt = T/N(n);

    for j=1:J

        W(1) = 0;

        Y(1) = X_0;

        for i=1:N(n)

            dW = sqrt(dt)*randn;

            W(i+1) = W(i) + dW;

            Y(i+1) = Y(i) + mu*Y(i)*dt + sigma*Y(i)*dW;

        end

        Y_N(j) = Y(N(n)+1);

        X_T(j) = X_0*exp((mu - 0.5*sigma^2)*T + sigma*W(N(n)+1));

    %epsilon(n) = abs(mean(X_T) - mean(Y_T));

    epsilon(n) = abs(var(X_T) - var(Y_N));

    end

end

line_fit = polyfit(log(N)/log(2),-log(epsilon)/log(2),1)

plot(log(N)/log(2),-log(epsilon)/log(2),’+’)

hold on

plot(log(N)/log(2),line_fit(1)*log(N)/log(2) + line_fit(2), ’:’)

Simulation 30.2 (Milstein Scheme: Strong Convergence)

We test the speed of strong convergence of the Milstein scheme for solving the geometric Brownian motion.

T = 1;

N = [2^4,2^5,2^6,2^7,2^8,2^9,2^10];

J = 10^4;

Error=zeros(1,J);

mu = 0.5;

sigma = 0.6;

X_0 = 10;

for n=1:length(N)

    dt = T/N(n);

    t = [0:dt:T];

        for j=1:J

            W(1) = 0;

            Y(1) = X_0;

            for i=1:N(n)

            dW = sqrt(dt)*randn;

            W(i+1) = W(i)+dW;

            Y(i+1) =Y(i)+mu*Y(i)*dt+sigma*Y(i)*dW+sigma^2/2*Y(i)*(dW^2-dt);

            end

         X_T = X_0*exp((mu - 0.5*sigma^2)*T + sigma*W(N(n)+1));

         Error(j) = abs(X_T - Y(N(n)+1));

        end

    epsilon(n) = mean(Error);

end

line_fit = polyfit(log(N)/log(2),-log(epsilon)/log(2),1)

plot(log(N)/log(2),-log(epsilon)/log(2),’+’)

hold on

plot(log(N)/log(2),line_fit(1)*log(N)/log(2) + line_fit(2), ’:’)

Exercises

30.1. Let $\delta t = \frac{T} {L}$ and t _i  = i δ t. Consider the geometric Brownian motion

$$\displaystyle{\frac{S(t_{i+1}) - S(t_{i})} {S(t_{i})} =\mu \,\delta t +\sigma \sqrt{\delta t}\;Y _{i}}$$

where $\mu,\sigma$ are positive constants and Y ₀, Y ₁, Y ₂, … are independent standard normal variables.

• (i) What is the distribution of $\log \left (\dfrac{S(t)} {S_{0}} \right )$? Justify your answer.

• (ii) Find

  $$\displaystyle{\lim _{\delta t\rightarrow 0+}\;\frac{1} {\delta t}\;\mathbb{E}\bigg[\left (\frac{S(t_{i+1}) - S(t_{i})} {S(t_{i})} \right )^{2}\bigg]\;.}$$

30.2. Compare the exact solution obtained in Problem 12.3 for the SDE

$$\displaystyle{\mathrm{d}X_{t} =\mathrm{ d}t + 2\sqrt{X_{t}}\,\mathrm{d}W_{t}}$$

with a numerical solution obtained by the Milstein scheme.

30.3. Compare the exact solution obtained in Problem 12.4 for the SDE

$$\displaystyle{\mathrm{d}X_{t} = -X_{t}(2\log X_{t} + 1)\mathrm{d}t + 2X_{t}\sqrt{-\log X_{t}}\,\mathrm{d}W_{t}}$$

with a numerical solution obtained by the Milstein scheme.