RETROSPECTIVE EXACT SIMULATION 193
This Brownian meander over [0,1] can be flipped and rescaled to provide a way
of connecting the point (0,0) to (t,b). Then a second Brownian meander can be used
to connect the point (t,b) to (T, a).
Lemma 10.9. Let {B
meander,a
t
} be a Brownian meander over time interval [0, 1] with
value 0 at time 0 and value a at time 1. Let B
t
be Brownian motion conditioned to
pass through the points (0,0), (t,b), and (T,a) with B
t
(t) ≥ b for all t ∈[0,T ].Set
B
s
=
√
t ·B
meander,−b/
√
t
(t−s)/t
+ bfors∈[0,t]
B
s
=
√
T −t ·B
meander,(a−b)/
√
T −t
(s−t)/(T−t)
+ bfors∈[t,T ].
Then {B
s
|B
0
= 0,B
t
= b,B
T
= a,(∀r ∈ [0,T ])(B
r
≥ b)}
s∈[0,T ]
∼{B
s
}
s∈[0,T ]
.
This lemma is Theorem 2 of [11], which in turn was Proposition 2 of Asumussen
et al. [4] rescaled to be over the interval [0,T ]. Putting this lemma in algorithmic
form gives us a way to generate the Brownian motion through (0, 0)(t, b),and(T,a)
at an arbitrary number of values.
BM given min Input: b, t, a, (t
1
,...,t
n
), T Output: (B
t
1
,...,B
t
n
)
1) k ← max{j ≤ n : t
j
< t}
2) If k > 0
3) t
← ((t −t
1
)/t,...,(t −t
k
)/t)
4) For j from 1 to 3, (X
j
1
,...,X
j
k
) ← Standard Brownian Bridge(t
)
5) For j from 1 to k
6) B
t
j
← b +
√
t ·
#
([−b/
√
t]t
j
+ X
1
j
)
2
+(X
2
j
)
2
+(X
3
j
)
2
7) If k < n
8) t
← ((t
k+1
−t)/(T −t),...,(t
n
−t)/(T −t))
9) For j from 1 to 3, (X
j
1
,...,X
j
n−k
) ← Standard Brownian Bridge(t
)
10) For j from k + 1ton
11) B
t
j
← b +
√
T −t ·
#
([(a −b)/
√
T −t]t
j−k
+ X
1
j−k
)
2
+(X
2
j−k
)
2
+(X
3
j−k
)
2
So the outline of the procedure is
• Find the minimum of B
t
over [0,T ].
• Use the Brownian meanders to piece together a Brownian motion over [0 , T ] that
passes through the minimum.
• Use the knowledge of the smallest the Brownian motion can be to obtain a bound
(B
t
) ≤ M.
• Now use retrospective sampling as before.
Putting all this together gives the following algorithm.
194 STOCHASTIC DIFFERENTIAL EQUATIONS
Retrospective Sampling for SDEs 2 Input: T , x
0
Output: X ∼X
T
1) X ←x
0
2) Repeat
3) Draw R from density f
R
(u) ∝ exp(A(u) −(u −X)
2
/2), a ← 1
4) (b,t) ← Minimum
Brownian Bridge(T,y −x )
5) M ← max
u∈[b+x,∞)
(u)
6) i ← 1, U ← Unif([0,1]), t
1
←−(1/M)ln(U)
7) While t
i
≤ T
8) U ←Unif([0,1]), i ← i + 1, t
i
←t
i−1
+(1/M)ln(1/U )
9) If i > 1
10) (X
1
,...,X
i−1
) ← BM given min((z
1
,z
2
),y −x, (t
1
,...,t
i−1
))
11) (V
1
,...,V
i−1
) ← Unif([0,1]
i−1
)
12) a ←
∏
i
i=1
1(V
i
≤ X
j
/M)
13) Until a = 1
14) X ← R
10.3.2 Example: stochastic logistic growth model
As an example of the algorithm Retrospective
Sampling for SDEs 2 , consider
the stochastic logistic growth model:
dV
t
= rV
t
(1 −V
t
/K) dt +
β
V
t
dB
t
. (10.21)
Here r, K,and
β
are known positive parameters, and say V
0
= v
0
∈ (0,K) is also a
given parameter.
This model is used for population size when resources are limited. The parameter
K controls how large V
t
can get, and is known as the carrying capacity of the model.
As noted in [11], it can be shown tha t with probability 1, f or v
0
∈ (0,K), V
t
∈ (0,K)
for all t with pr obability 1 (see [76, Section 15.7] .) The parameter
β
controls the size
of the random variation in population.
Following [11], use a slightly different transformation than given previously,
namely, X
t
=
η
(V
t
),where
η
= −
x
z
b(v)
−1
du.Hereb(v)=
β
v,so
η
(v)=
−
β
−1
[ln(v) −ln(z)].Setz = 1tomakex =
η
(v)=−
β
−1
ln(v), or equivalently,
v = exp(−
β
x).
So
α
(x)=[a(v)/b(v) −1/2]=
β
r(1 −V
t
/K) −1/2 =
β
r(1 −exp(−
β
X
t
)/K) −
1/2 and the SDE of interest is
dX
t
=
β
2
−
r
β
+
r exp(−
β
X
t
)
β
K
dt + dB
t
. (10.22)
The function in front of dt is
α
(X
t
). The next step is bounding (1/2)(
α
2
+
α
):
(1/2)(
α
2
+
α
)(u)=
1
2
β
2
−
r
β
2
−2
r
2
β
2
K
exp(−
β
u)+
r
2
β
2
K
2
exp(−2
β
u)
.
(10.23)
RETROSPECTIVE EXACT SIMULATION 195
The right-hand side is bounded below by (1/2)(
β
2
/8 −r/2forallu ∈ R. Hence
(u)=
1
2
r
2
β
2
−2
r
2
β
2
K
exp(−
β
u)+
r
2
β
2
K
2
exp(−2
β
u)
. (10.24)
The function (u) was designed so that (u) > 0. When u > 0 (u) ≤
(1/2)(r
2
/
β
2
), but that leaves the situation when u < 0 to worry about.
So use the ideas of the last section: find the minimum value of B
t
over [0,T ],then
that gives a maximum value of (B
t
) over [0,T ]. With that maximum value in place,
it once again becomes possible to generate a Bernoulli with mean exp(−I) where
I =
T
0
(B
t
) dt.
Therefore the techniques of the last section can be applied as long as A(u) does
not grow too quickly. So consider A(u)=
x
0
α
(s) ds.Here
A(u)=
β
2
−
r
β
u −
r
β
2
K
exp(−
β
u). (10.25)
Since A(u) grows more slowly than quadratically, it will be possible to normalize the
density of B
T
.
To be specific, for x
0
= −ln(v
0
)/
β
, it is necessary to be able to sample B
T
from
density
exp(A(u) −(u −x
0
)
2
/(2T )) ∝ exp(−(u −g
1
)
2
/(2T ) −g
2
exp(−
β
u)), (10.26)
where g
1
= x
0
+ T (
β
/2 −r/
β
) and g
2
= r/(
β
2
K) are constants. This can be accom-
plished quickly by using AR from a normal with mean g
1
+ T
β
g
2
exp(−
β
g
1
) and
variance T .
10.3.3 Unbounded
To deal with the case where is an unbounded function, it is necessary to find a value
M > 0 such that the Brownian motion stays between M and −M from [0,T ].In[10],
Beskos et al. found such a method by generating a Brownian bridge whose extreme
values were bounded.
An alternate method comes from [22]. Recall from Section 2 .6.1 that for a Brow-
nian motion {B
t
} with T
1
= inf{t : |B
t
| = 1}, it is possible to simulate from T
1
in
finite expected time using AR.
Suppose that the goal is to find the solution to the SDE at time T .IfT
1
> T ,then
|B
t
|≤1forallt ∈ [0 , T ], and the value of can be bounded appropriately using this
fact.
On the other hand, if T
1
< T ,letT
2
= inf{t > T
1
: |B
t
−B
T
1
| = 1}. Then for all
t ∈ [T
1
,T
2
], B
T
1
−1 ≤ B
t
≤B
T
1
+ 1. In g eneral, letting T
i+1
= inf{t > T
i
: |B
t
−B
T
i
|=
1} gives a sequence of passage times where the Brownian motion has moved at most
one away from its previous value. By the symmetry of Brownian motion, B
T
i+1
is
equally likely to be eith er B
T
i
+ 1orB
T
i
−1. See Figure 1 0.1 for an illustration.
Recall that to generate the Brownian motion {X
t
}that is a candidate for a solution
196 STOCHASTIC DIFFERENTIAL EQUATIONS
0
T
1
T
2
T
3
T
4
T
5
T
0
T
0
T
Figure 10.1 Generating the passage times gives an upper and lower bound on the Brownian
motion. The Brownian motion must pass through the circles and stay in the gray shaded area.
to the ODE, first X
T
is drawn, then a Brownian bridge that runs from x
0
at time 0 to
X
T
at time t can be constructed as
X
t
= x
0
+(t/T )(X
T
−x
0
+ B
T
−B
t
). (10.27)
Since |B
t
|≤N = sup{i : T
i
< T }, |X
t
|≤x
0
+ |X
T
−x
0
+ N|, which gives a cor-
responding bound M = max
u:|u|≤x
0
+|X
t
−x
0
+N|
(u) on the function. What is needed
at this point is a way to generate B
t
for a finite set of times in [T
i−1
,T
i
] given B
T
i−1
and B
T
i
. From the Strong Markov Property of Brownian motion, this is equivalent to
generating B
t
for a finite set of times in [0, T
1
], and then just adding T
t
i−1
.
Note that if B
t
is Brownian motion conditioned to start at 0 and end at 1 at T
1
,
then
˜
B
t
= 1 −B
T
1
−t
is a Brownian meander conditioned to start at 0 and end at 1 at
T
1
. The original B
t
satisfies |B
t
|≤1when
˜
B
t
≤ 2.
So to draw from the conditioned B
t
,itsuffices to draw from
˜
B
t
, then accept only
when
˜
B
t
≤ 2. The following theorem gives a means for deciding when to accept o r
not, given
˜
B
t
at a finite number of time points in [0,T
1
].
Lemma 10.10 (Theorem 4.2 of [22]). Suppose for times t
1
,...,t
n
in [0,T
1
],
˜
B
t
i
= y
i
.
The chance that (y
1
,...,y
n
) should be accepted as a draw from [
˜
B
t
|max
˜
B
t
≤2] is
P( max
t∈[0,T
1
]
˜
B
t
≤2)
−1
n
∏
i=1
p(t
i
,y
i
;t
i+1
,y
i+1
) ·q(t
1
,y
1
) ·1(y
i
∈ (0,2)), (10.28)
where
p(s,x;t,y)=
1 −
∑
∞
j=1
(
θ
j
(s,x;t,y) −
ϑ
(s,x;t,y))
1 −exp(−2xy/(t −s))
,
θ
j
(s,x;t,y)=exp
−
2(2 j −x)(2 j −y)
t −s
+ exp
−
2(2( j −1)+x)(2(j −1)+y)
t −s
,
RETROSPECTIVE EXACT SIMULATION 197
ϑ
j
(s,x;t,y)=exp
−
2 j(4 j + 2(x −y))
t −s
+ exp
−
2 j(4 j −2(x −y))
t −s
,
q(s,x)=1 −
1
x
∞
∑
j=1
(
ρ
j
(s,x) −
˜
ρ
j
(s,x))
ρ
j
(s,x)=(4 j −x)exp
−
4 j(2 j −x)
s
˜
ρ
j
(s,x)=(4 j + x)exp
−
4 j(2 j + x)
s
.
Once again the probability of accepting has been bounded by an alternating se-
ries, and so the AR method of Section 2.6 can be used to obtain draws.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.