DOMINATED COUPLING FROM THE PAST FOR POINT PROCESSES 131
chain consists of a pair of point processes A ⊆ B ⊆ D su ch that the state X always
satisfies A ⊆ X ⊆ B.
Points in A are definitely in the state X , but points in BA
C
might be in X ,orthey
might not be.
The idea of coupling behind dominating CFTP can also be used to better esti-
mates of ergodic averages, see [99, 100]. In addition, it can also be used for thinning
and transformation of spatial processes, which in turn can be useful for model as-
sessment [104, 97].
7.4.1 Example: dominated CFTP for the Strauss process
For Strauss, and A ⊆ X ⊆ B, the lowest chance of a point v being added is when
X = B, and the highest chance is when X = A. So the bounding states can be updated
as follows, given an event list.
Strauss bounding update
Input: event list EL with n events, D(−n) Output: A, cflag
1) A ← /0, B ← D(−n)
2) For i from n to1do
3) Let (type vU) be the nth event in EL
4) If type is death then
5) A ← A −v, B ← B −v
6) Else
7) p
R,A
(v) ← #{w ∈ A :dist(v,w) ≤ R}
8) p
R,B
(v) ← #{w ∈ B :dist(v,w) ≤ R}
9) If U <
γ
p
R,B
then A ← A + v
10) If U <
γ
p
R,A
then B ← B + v
11) If A = B then cflag is true
Further examples of dominating CFTP for spatial point processes are discussed
in [6, 5].
7.4.2 Running time
To understand how long this process must be run before coalescence occurs, it helps
to understand how exponential random variables work over small time steps.
Suppose that A ∼ exp(
λ
). Then conditioned on A > t, P(A ∈ (t,t + h]|A > t)=
λ
h + o(h). Hence for each of the points in A
t
or B
t
(or both), the chance that the point
dies in interval [t,t + h] is
λ
h + o(h).
Points that are in B
t
A
t
that die help coalescence occur, since this brings the sets
A
t
and B
t
closer together. For B
t
and A
t
to move farther apart, a point must be born
within distance R of a point in B
t
A
t
,andU >
γ
. Hence the chance that B
t
A
t
grows
by a point is bounded above by
βν
(B
R
)(1 −
γ
)h + o(h).Here
ν
(B
R
) is the maximum
size of a ball of radius R for a point in the space.
Using this gives the following lemma.
132 SPATIAL POINT PROCESSES
Lemma 7.5. Consider an interval of time [t,0],whereA
t
= /0 and B
t
= D
t
∩S, where
D
t
is the dominating process. Then the chance that A
0
= B
0
is at most
βν
(S)exp(−[1 −(1 −
γ
)
βν
(B
R
)]t). (7.6)
Proof. Let N
t
= #(B
t
A
t
). Then if a point in B
t
A
t
dies, N
t
is reduced by one; if a
point is born within distance R of B
t
A
t
and U >
γ
,thenN
t
grows by one.
So for t ∈ [t
,0] and h > 0:
E[N
t+h
|F
t
] ≤ N
t
−hN
t
+ h(1 −
γ
)
βν
(B
R
)N
t
+ o(h). (7.7)
Letting n
t
= E[N
t
] and taking the expectation of both sides gives
n
t+h
≤ n
t
−hn
t
+ h(1 −
γ
)
βν
(B
r
)n
t
+ o(h). (7.8)
Subtracting n
t
, dividing by h, and taking the limit as h goes to 0 gives n
t
≤ [
β
(1 −
γ
)
ν
(B
r
) −1]n
t
.
This differential inequality gives the upper bound n
t
≤ n
t
exp([
β
(1 −
γ
)
ν
(B
R
) −
1](t −t
)). The number of points in D
t
is Poisson with mean
βν
(S), which completes
the proof.
Therefore, as long as the parameters are in the regime wher e (1 −
γ
)
βν
(B
R
) < 1,
efficient generation from the Strauss process is possible.
7.5 Shift moves
The running time results indicate that when
β
is small, the procedure will be efficient.
This result uses the birth and death moves introduced by Preston [111]. By adding a
third type of move, a shift move [55], it is possible to improve the analysis further.
A shift move can be viewed as when one point is added while another is de-
stroyed. This is equivalent to shifting the point from one location to another. The
governing equation for shifts is similar to that for births and deaths.
Theorem 7.5 ([55]). Let b(x,v) be the rate at which a point v is born to configuration
x, let d(x + v,v) be the rate at which point v in configuration x + v is dying, let s(x +
v,v, w) be the rate at which point v in configuration x + v is being shifted to point
w, and let s(x + w,w,v) be the rate at which point w in configuration x + wisbeing
shifted to point v. Suppose
f (x)b (x, v)= f (x + v)d(x + v, v)
f (x + v)s(x + v, v,
w)= f (x + w)s(x + w,w, v).
Then f is a stationary density for the jump process.
Recall Preston’s approach, which keeps deaths occurring at a constant rate of 1,
and then just modifies the birth rate. I n order to keep th ings simple, the shifts can be
just a subset of the births.
Here is the idea. In a process like the Strauss process, there is a proposed birth
SHIFT MOVES 133
v. There are a number of neighbors w
1
,...,w
k
where each has a
γ
chance (indepen-
dently) of not affecting the birth of v in the slightest.
However, it could be that exactly one neighbor is blocking the draw of v.Inthis
case, flip a p
s
-coin, and if it comes up heads, keep the birth and kill the neighbor. In
other words, shift the neighbor w to v.
This move maintains both the number of points in the configuration and the num-
ber of pairs within distance R of each other. Also, the rate of shifting from x + v −w
to x + w −v are exactly equal, so the conditions of the theorem are satisfied.
This gives rise to the following pseudocode.
Strauss shift update Input: current x, Output: next x
1) Draw T
B
← Exp(
βν
(S))
2) Draw T
D
← Exp(#x)
3) If T
D
< T
B
(then there is a death)
4) Draw v uniformly from x, x ← x −v
5) Else
6) Draw v over
ν
(S)
7) N
v
←{w :dist(v,w) ≤ R}
8) For each w ∈ N
v
9) Draw C ← Bern(
γ
),IfC = 1thenN
v
← N
v
−w
10) If #N
v
= 0or(#N
v
= 1andU < p
s
)
11) x ← x N
v
+ v
Now examine how to update the bounding chain. Recall that the bounds are A ⊆
x ⊆ B, so that points in A are definitely in the configuration, while points in B A
might be in the configuration, or they might not be. So both possibilities have to be
considered when deciding what to do at the next step.
Let N
A,v
= {w ∈ A :dist(v,w) ≤ R},andN
B,v
= {w ∈ B :dist(v, w) ≤ R}.Then
each point in N
B,v
is retained independently with pro bability 1 −
γ
. If it is removed
from N
B,v
, it is also removed from N
A,v
. Now there are three cases to consider.
Case 1: #N
A,v
= #N
B,v
= 0. This is the easiest case, since here v will be born
regardless of whether or not a shift is attempted.
Case 2: #N
A,v
= 0, #N
B,v
= 1. This is an interesting case. Suppose a shift is at-
tempted. Then the fact that there is a w ∈ N
B,v
N
A,v
means that this point w might or
might not be part of the configuration. If it is not part of the configuration, then the
point v is born normally. If it is part of the configuration, then w is shifted to v. Eith er
way , w is now removed from the configuration, and v is added!
Case 3: #N
A,v
= 1, #N
B,v
> 1. When there is no shift move then the point in N
A,v
prevents v from being born. When there is a shift move, bad things happen: v might
or might not be born, and the point w ∈ N
A,v
might or might not be shifted away. The
result is that v and w are both removed from A andaddedtoB.
Case 4: #N
A,v
= 0, #N
B,v
> 2. In this case, whether or not there is a shift move
thefateofv is u ncertain, and so v is added to B but not to A.
This is summarized in the following pseudocode.
Strauss shift bounding update Input: x, A, B Output: x, A, B
134 SPATIAL POINT PROCESSES
1) Draw T
B
← Exp(
βν
(S))
2) Draw T
D
← Exp(#x)
3) If T
D
< T
B
(then there is a death)
4) Draw v uniformly from x, x ← x −v
5) Else
6) Draw v over
ν
(S)
7) N
A,v
←{w ∈ A :dist(v, w) ≤ R}, N
B,v
←{w ∈ B :dist(v, w) ≤ R}
8) For each w ∈ N
B
9) Draw C ← Bern(
γ
),IfC = 1thenN
B,v
← N
B,v
−w and N
A,v
← N
A,v
−w
10) If #N
A,v
= #N
B,v
= 0
11) A ← A + v, B ← A + v
12) Else if #N
A,v
= 0, #N
B,v
= 1
13) If U < p
s
then A ← A + v, B ← A + v N
B,v
14) Else B ←A + v
15) Else if #N
A,v
= 1, #N
B,v
≥ 1
16) If U < p
s
then A ← A + v N
A,v
, B ← A + v
17) Else if #N
A,v
= 0, #N
B,v
≥ 2
18) A ← A, B ← A + v
Lemma 7.6. Consider an interval of time [t,0],whereA
t
= /0 and B
t
= D
t
∩S, where
D
t
is the dominating process. Then the chance that A
0
= B
0
in the bounding update
with shifts with p
S
= 1/4 is at most
βν
(S)exp(−[1 −(1/2)(1 −
γ
)
βν
(B
R
)]t). (7.9)
Proof. As earlier, let N
t
= #(B
t
A
t
), n
t
= E[N
t
], and consider what happens in a tiny
time interval of length h.
There could be a death of a point in B
t
A
t
, reducing N
t
by 1. Then there are
the births to consider. Given the chosen birth point v, divide the space S into fo ur
subregions corresponding to the four cases.
A
0
= {s :#N
A,v
= 0,#N
B,v
= 0}
A
1
= {s :#N
A,v
= 0,#N
B,v
= 1}
A
2
= {s :#N
A,v
= 1,#N
B,v
≥ 1}
A
3
= {s :#N
A,v
= 0,#N
B,v
≥ 2}
Points born into A
0
do not change N
t
. A point born into A
1
decreases N
t
if U < p
s
,
otherwise it increases it by 1. Points born into A
2
can increase N
t
by 2 if U < p
s
,
otherwise N
t
is unchanged. Last, points born into A
3
always increase N
t
by 1.
Putting this together, the overall ra te of change in n
t
is
n
t+h
≤n
t
−hn
t
+ hE[
ν
(A
1
)(−p
s
+(1 − p
s
))] + hE[
ν
(A
2
)][2p
s
]+hE[
ν
(A
3
)] + o(h)
= n
t
+ h[−n
t
+(1 −2p
s
)E[
ν
(A
1
)] + 2p
s
E[
ν
(A
2
)] + E[
ν
(A
3
)]]
= n
t
+ n
t
h[−1 +(1/2)E[
ν
(A
1
)+
ν
(A
2
)+2
ν
(A
3
)]]
CLUSTER PROCESSES 135
where the last line follows from setting p
s
= 1/4.
Note that any point in A
3
neighbors at least two points in B A, while points in
A
2
and A
1
neighbor at least one. The expected number of points to survive the
γ
-coin
weeding process is (1 −
γ
)n
t
. Since each covers an area of measure
ν
(B
R
),andthe
intensity is
β
, that means that
E[
ν
(A
1
)+
ν
(A
2
)+2
ν
(A
3
)] ≤ (1 −
γ
)n
t
βν
(B
R
). (7.10)
Hence
n
t+h
≤ n
t
+ n
t
h[−1 +(1/2)(1 −
γ
)
β
]+o(h).
Solving the differential inequality gives the result.
Notice that the inclusion of the shift move has improved the analysis to the point
where twice as large values o f
β
are now shown to run efficiently!
7.6 Cluster processes
Another common model for spatial data is a cluster p rocess. Here the set of parent
points follows a PPP, and then each parent point (possibly) gives rise to more d augh-
ter points. The collection of daughter points forms the cluster process. These types
of point processes arise naturally in situations such as disease points or plant growth.
Consider such a point process that lives in the plane. Suppose that the goal is
to simulate such a process perfectly over a finite observation window. Then one ap-
proach would be to simulate the parent process in the window, and then the daughter
points.
This, however, will give a simulation with too few points: it could be that a parent
point outside of the observation window could give rise to a daughter point that falls
back inside the observation window.
Brix and Kendall [15] noted that this problem could be solved by simulating
exactly those parent points on the infinite plane that gave rise to daughter points that
lie inside the observation window.
Let W denote the observation window. In the g eneral case, allow each parent
point x to have a random mark mark M, so that each point is of the form [x; M].This
mark should have finite expectation (E[M] < ∞).
Furthermore there is an intensity k(x,·) for daughter points that depends on the
location of the parent point x. Then each parent point has a set of daughter points that
is a PPP with intensity Mk(x,·).
So for a parent point x, what is the chance that it has a daughter point that falls in
W ? Well, the daughter points inside W from x form a PPP, and the chance that a PPP
contains at least one point is 1 −exp(−
μ
),where
μ
is the mean number of points
that fall inside the window.
To find the mean number of points, first let K(x,W )=
y∈W
k(x,·) dR
2
.That
would be the mean number of daughter points to fall in W if the mark M was always
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.