Chapter 10
Stochastic Differential Equations
If God has made the world a perfect mechanism, He has at least conceded
so much to our imperfect intellect that in order to predict little parts of it, we
need not solve innumerable differential equations, but can use dice with fair
success.
Max Born
Diffusion models appear throughout applied mathematics, and form a natural
stochastic generalization of differential equations (DEs). In a first-order DE such
as dy = f (y,t) dt , the idea is that as time advances a small amount h,thevalueof
y changes by the small amount f (y,t) ·h. This naturally gives rise to a numerical
method: keep updating time by adding h to the current time value at each step, while
updating y by adding f (y,t) ·h to the current y value at each step. For many DE’s,
only such numerical solutions are possible.
The above algorithm is known as Euler’s method, and is the simplest way to nu-
merically solve a first-order differential equation. Of course, more advanced methods
exist (see for instance [68].) Typically, as h goes to 0, the numerical error in the ap-
proximation goes to 0 as well. Still, all such methods are always approximate. Except
under unusual circumstances, there will always be numerical error.
The idea of a stochastic differential equation (SDE) is to improve the model by
adding random movement through the use of a differential Brownian motion, dB
t
.
An SDE might have the form
dX
t
= a(X
t
) dt + b(X
t
) dB
t
. (10.1)
Very roughly speaking, dB
t
can be thought of as a normal random variable that has
mean 0 and variance dt .WhenZ is a standard normal random variable with mean
0 and variance 1, then cZ has mean 0 and variance c
2
. Therefore, an approach to
numerically so lving an SDE is to use
X
t+h
= X
t
+ a(X
t
)h + b(X
t
)
√
hZ. (10.2)
For small h,
√
h is very much larger than h. Therefore, the normal random vari-
able
√
hZ with standard deviation
√
h is spread out much wider than the deterministic
part a(X
t
)h.Forh of order (b(X
t
)/a(X
t
))
2
, there is a chance (as with the multishift
coupling from Chapter 6) that the randomized part of the update is independent of
183
184 STOCHASTIC DIFFERENTIAL EQUATIONS
the deterministic part. This is essen tially the property that allows perfect simulation
to occur.
Suppose Y
t+1
= X
t
+
√
hZ is put forward as the next candidate for X
t+1
.Then
there should be a reasonable chance of accepting Y
t+1
as a perfect draw from X
t
.
Unfortunately, it is unknown how to compute the probability of acceptance for this
simple scheme.
Therefore, a more sophisticated approach using densities of the solution of the
SDE with respect to Brownian motion will b e used. However, these densities are
very difficult to compute exactly, and so new Monte Carlo methods were created for
generating Bernoulli random variables with the correct mean. To understand these
methods, a deeper understanding of Brownian motion is necessary.
10.1 Brownian motion and the Brownian bridge
Definition 10.1. A stochastic process {B
t
} is standard Brownian motion if
1. B
0
= 0.
2. The map t →B
t
is continuous with probability 1.
3. For a ≤ b ≤ c ≤ d, B
d
−B
c
is independent of B
b
−B
a
.
4. For a ≤ b, B
b
−B
a
∼ N(0,b −a).
A Brownian motion pro cess is defined for all t ∈ R, therefore, it is not possible
to write down (let alone simulate) an entire Brownian motion process at once.
A more achievable goal is to simulate standard Brownian motion at a finite set
of times 0 < t
1
< t
2
< t
3
< ···< t
n
. Since all the differences B
t
i
−B
t
i−1
are normally
distributed, the joint distribution of (B
t
1
,...,B
t
n
) will be multivariate Gaussian.
For a standard normal random variable Z ∼ N(0,1) and a constant k, kZ ∼
N(0,k
2
).ThensinceB
t
1
−B
0
∼ N(0,t
1
), simply generate a standard normal random
variable Z
1
∼ N(0,1),andletB
t
1
be B
0
+ Z
1
√
t
1
. Continuing in this fashion, let B
t
i+1
be B
t
i
+ Z
i
√
t
i+1
−t
i
,whereZ
1
,...,Z
n
are iid N(0,1).
Standard Brownian Motion
Input: 0 < t
1
< t
2
<... <t
n
, Output: B
t
1
,B
t
2
,...,B
t
n
1) t
0
← 0,, B
0
← 0
2) For i from 1 to n
3) Draw Z a standard normal random variable
4) B
t
i
← B
t
i−1
+ Z
√
t
i
−t
i−1
Of course, it is often the case that the Brownian motion needs to start at a location
other than 0.
Definition 10.2. Let {B
t
} be standard Brownian motion. Then B
x
t
= B
t
+ xisBrow-
nian motion started at x.
Brownian motion where the values of B
0
and B
T
are fixediscalledaBrownian
bridge or pinned Brownian motion. (In some texts this terminology is reserved for
Brownian motion where B
0
= B
T
= 0, but here it will be used for any fixed values
AN EXPONENTIAL BERNOULLI FACTORY 185
for B
0
and B
T
.) Given the ability to simulate Br ownian motion, the following lemma
gives a fast way to simulate a Brownian bridge.
Lemma 10.1. Let {B
t
}
t∈[0,T ]
be standard Brownian motion. Then
R
x,y
t
= x + B
t
−(t/T )(x + B
T
−y) (10.3)
has the same distribution as [{B
t
}
t∈[0,T ]
|B
0
= x, B
T
= y].
See [7] for a proof. The corresponding algorithm is as follows.
Standard Brownian Bridge
Input: 0 < t
1
< t
2
<... <t
n
, x, y, T Output: B
t
1
,B
t
2
,...,B
t
n
1) (B
t
1
,...,B
t
n
,B
T
) ← Standard Brownian Motion(t
1
,...,t
n
,T )
2) For i from 1 to n
3) R
t
i
← x + B
t
i
−(t
i
/T )(x + B
T
−y)
Generating from Brownian motion and Brownian bridges is easy, but generating
from general SDE’s will require more tools, in particular, an exponential Bernoulli
factory.
10.2 An exponential Bernoulli factory
The algorithm for generating from more general SDE requires the use o f accep-
tance/rejection. In Section 2.2, it was shown how to use AR to sample from one
density f given a draw from another density g. To use the algorithm, it is necessary
to have c such that c ≥ f (x)/g(x) for all x in the state space Ω, and the ability to draw
from Bern( f (x)/[cg(x)] for all x ∈ Ω. The method for doing so will utilize what is
known as a Bernoulli factory .
To understand what a Bernoulli factory does, it helps to have some examples.
Suppose that X
1
,X
2
,...are iid Bern(p), and so give an infinite stream of independent
coin flip s with probability p of heads. Suppose the goal is to build a new coin out of
these X
i
that h as probability 2p − p
2
of heads. That turns out to be easy. Just let
Y = 1(X
1
= 1orX
2
= 1).
This Bernoulli factory uses either 1 or 2 coin flips. If X
1
= 1, then there is no need
to look at X
2
. The chance that the second coin is necessary is 1 − p. Therefore if T
represents the number of coins that need to be examined, E[T ]=1+(1 −p)=2−p.
An early Bernoulli factory that uses a random number of coin flips is due to
Von Neumann [127]. In this factory, the goal is to generate Y ∼ Bern(1/2),and
this technique was used to go from possibly unfair coin flips to fair coin flips. This
Bernoulli factory is
T = inf{t : (X
2t+1
= 1,X
2t+2
= 0) or (X
2t+1
= 0,X
2t+2
= 1)}, Y = X
2T +1
.
This is essentially AR: keep flipping coins in pairs until either (1, 0) or (0,1) is
reached. Conditioned on one of these two events, each is equally likely to occur, so
Y ∼ Bern(1/2).
Following [50], a Bernoulli factory can be defined as follows.
186 STOCHASTIC DIFFERENTIAL EQUATIONS
Definition 10.3. Given p
∗
∈(0,1] and a function f : [0, p
∗
] →[0,1],aBernoulli fac-
tory is a computable function A that takes as input a number u ∈ [0,1] together with
a sequence of values in {0,1}, and returns an output in {0,1} where the following
holds. For any p ∈ [0, p
∗
],X
1
,X
2
,... iid Bern(p), and U ∼ Unif([0, 1]),letTbethe
infimum of times t such that the value of A (U, X
1
,X
2
,...) only depends on the values
of X
1
,...,X
t
.Then
1. T is a stopping time with respect to the natural filtration and P(T < ∞)=1.
2. A (U,X
1
,X
2
,...) ∼ Bern( f (p)).
Call T the running time of the Bernoulli fa ctory.
Densities for SDE’s employ Girsanov’s Theorem [42], which gives the density
of the form exp(−p) for a specific p. Therefore, what is needed for these types of
problems is an exponential Bernoulli factory where Y ∼ Bern(exp(−p)).Beskoset
al. [11] gave the following elegant way of constructing such a Bernoulli factory.
Recall how thinning works (discussed in Sections 2.2 and 7.2.) Take P, a Poisson
point process of rate 1 on [0 , 1], and for each point in P flip a coin of probability p.
Then let P
be the points of P that received heads on their coin. P
will be a Poisson
point process of rate p. So the number of points in P
is distributed as Poisson with
mean p,whichmakesP(#P
= 0)=exp(−p).
More generally, suppose that A ⊂ B are sets in R
n
of finite Lebesgue measure.
Let P be a Poisson point process of rate 1 on B.ThenP ∩A is a Poisson point process
of rate 1 on A, and the chance that there are no points in A is exp(−m(A)),where
m(A) is the Lebesgue measure of A.
With this in mind, we are now ready to perfectly simulate some SDE’s.
10.3 Retrospective exact simulation
Retrospective exact simulation is a form of acceptance/rejection introduced by
Beskos et. al [11] to handle SDE’s. Start with Equation (10.1).
The SDE has a unique solution, that is, there exists a unique distribution of {X
t
}
for t ∈ [0, T ], given that the functions a and b satisfy some regularity conditions.
These conditions ensure that the SDE does not explode to infinity in fin ite time. See
Chapter 4 of Kloeden and Platen [83] for details.
Our original SDE had the form dV
t
= a(v) dt + b(v) dB
t
.Thefirst step to note
is that for many a and b it is possible to restrict our attention to SDE’s where b(v) is
identically 1.
To see th is, consider the differential form of It¯o’s Lemma (see for instance [110]).
Lemma 10.2 (It¯o Lemma (1st form)). Let f be a twice differentiable function and
dV
t
= a(v) dt + b(v) dB
t
. Then
df(V
t
)=[a(v) f
(v)+b(v)
2
f
(v)/2] dt + b(v)f
(v) dB
t
. (10.4)
Now let
η
(v)=
v
z
b(u)
−1
du for any z in the state space Ω.Then
η
(v)=b(v)
−1
and
η
(v)=−b
(v)/b(v)
2
. Hence for X
t
=
η
(V
t
),
dX
t
=[a(v)/b(v)−b
(v)/2] dt + dB
t
. (10.5)
RETROSPECTIVE EXACT SIMULATION 187
If mor e convenient, the transformation
η
2
(v)=−
v
z
b(u)
−1
du can be used. This
leads to dX
t
= −[a(v)/b(v) −b
(v)/2] dt −dB
t
, but since B
t
∼−B
t
,thisalsogives
an SDE with unit coefficient in front of the dB
t
:
dX
t
= −[a(v)/b(v) −b
(v)/2] dt + dB
t
. (10.6)
Let
α
(x)=b
(
η
−1
(x))/2 −a(
η
−1
(x))/b(
η
−1
(x)).When
α
is identically 0, then
dX
t
= dB
t
, and the solution is just X
t
= B
t
, standard Brownian motion. If the function
α
is close to 0 , then X
t
will be close to, but not exactly, Brownian motion. If it is close
to Brownian motion, then the chance of rejecting a pure Brownian motion as a draw
from X
t
will be fairly small.
Consider the density of the solution of the diffusion with respect to standard
Brownian motion. For example, suppose that X
t
has the same distribution as stan-
dard Brownian motion, but conditioned on X
1
≥ 1andX
2
≤ 2. Then the density of
{X
t
}
t∈[0,2]
with respect to standard Brownian motion is f
X
(x)=1(X
1
≥ 1 , X
2
≤ 2 ).
(This is an unnormalized density.) Since the density lies between 0 and 1 (inclusive),
it is straightforward to generate from X
t
over 0 < t
1
< ···< t
k
< 2. Simply generate
x =(x(0), x(t
1
),x(t
2
),...,x(t
k
),x(2)) as a standard Brownian motion, and accept the
draw as a draw from the law of X
t
with probability f
X
(x).
In fact, solutions to the SDE (10.6) have a density with respect to Brownian
motion started at th e same location as the solution to the SDE. This important fact is
known as Girsanov’s theorem [42].
To be precise, let C = C([0,T ],R) denote the set of continuous mappings from
[0,T ] to R,and
ω
∈C. Then one way to view Brownian motion starting at B
0
= x is
that it is a measure W
x
over C such that a random draw {B
t
}
t∈[0,T ]
from the measure
satisfies three properties: B
0
= x,forany0≤ t
1
< t
2
≤ t
3
< t
4
≤ T , B
t
4
−B
t
3
and
B
t
2
−B
t
1
are independent and B
t
2
−B
t
1
∼ N(0,t
2
−t
1
).
Let Q be the probability measure of solutions to the diffusion (10.6). Then Gir-
sanov’s theorem states that a draw from Q has a density with respect to W. In mea-
sure theory, this density is known as the Radon-Nikodym derivative between the two
measures, and is
dQ
dW
x
({
ω
t
})=exp
T
0
α
(
ω
t
) d
ω
t
−
1
2
T
0
α
2
(
ω
t
) dt
. (10.7)
Again note that if
α
(x)=0forallx ∈ R, then the density is just 1, indicating that
the solution to the SDE is just Brownian motion in this case.
If this density is bounded above by c, then to use AR, just d raw a standard Brow-
nian motion {B
t
}, and then accept with probability equal to (1/c)[dQ/dW]({B
t
}).
When B
t
is substituted for
ω
t
,thefirst integral being exponentiated is
T
0
α
(B
t
) dB
t
. This r efers to the It
¯
ointegralof
α
(B
t
) with respect to the Brown-
ian Motion B
t
. (See [110] for a formal definition.) For the It¯o integral, when th e
function
α
has a continuous first derivative, It¯o’s Lemma can be employed to rewrite
the integral. The simpler form of the lemma is needed he re.
Theorem 10.1 (It¯o’s Lemma (2nd form) [69]). For a function f (x) with two contin-
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.