Chapter 7
Spatial Point Processes
With dancing, you have to know spatial movement with somebody. It is
steps. It’s literally steps and knowing how close to be or how far away. You
have to have the beat in the right place with the camera.
Channing Tatum
Hundred-year oaks in a forest. Typos in a book. Raindrops on a parking lot. These
are examples of data sets that can be modeled using spatial point processes. In a
spatial point process, there is a state space S, and some subset of points in the space
comprise the p rocess. Usually the points mark an occurrence of some event. Town
locations on a map, a list of homes containing someone with a disease, any time the
data is locational in time or space, it can be modeled with a spatial point process.
The state space does not have to be purely geometric: if S = R
2
×(−∞,0],the
points could represent the location of the town and the time (with 0 denoting the
present) that the town was founded.
Among spatial point processes, the most common model is the Poisson point
process (PPP) and its variants. A PPP can be defined mathematically in two different
ways. The first approach utilizes the idea of a random measure. The second approach
comes at the process from a simulation point of view. Naturally this second method
is of more value here!
Our basic presentatio n here follows notation from Streit [120]; see Chapter 1 of
that text for more detail. Throughout this chapter, S will denote the space in which
the points of the PPP occur. This space is often a subset of m-dimensional Euclidean
space S ⊆ R
m
. This space covers the examples treated in this chapter.
An element of a PPP is an unordered set of points in space. (A more general
definition of PPP allows repeated points in the space, but making the points distinct
allows for great simplification in the description and still covers most applications.)
This con figuration could contain no points, in which case it is empty, and written as
/0. As usual, let #P denote the number of points in the configuration P.LetS
[n]
denote
the set of size n subsets of S (note S
[0]
= {/0}.) Then the complete PPP is an element
of S
[0]
∪S
[1]
∪S
[2]
∪···, which is called the exponential space. (See [21] for a more
formal definition.)
Definition 7.1. Fo r S ⊂ R
m
,theintensity is a density with respect to Lebesgue mea-
sure over S so that for any A ⊆S of bounded size,
x∈A
λ
(x) dx < ∞.If
x∈A
λ
(x) dx =
0 for all A of measure 0, call the intensity continuous.
121
122 SPATIAL POINT PROCESSES
This of course does not imply that
S
λ
(x) dx is finite, only that every bounded
window is. Since the finiteness is only guaranteed for a bounded window, that is what
will be simulated from. Not the complete Poisson point process, but the finite number
of points that fall into some bounded window.
A PPP can be described by a simulation p rocedure that tells how to generate a
PPP over a set S
⊂ S where
x∈S
λ
(x) dx is finite.
Definition 7.2. A random set of points P in the exponential space of S is a Poisson
point process of continuous intensity
λ
if given P ∩A, the distribution of P ∩Bis
given by the following simulation technique:
1. Draw N ∼ Pois(
x∈B∩A
C
λ
(x) dx).
2. Draw P
1
,...,P
N
independently from unnormalized measure
λ
over BA
C
.
When
λ
= 1 everywhere, call this the standard PPP over the space.
Note that if
λ
= 1, the PPP drawn can be viewed as coming from a distribution
that has a density with respect to a different PPP.
Lemma 7.1. Let P
1
denote a PPP with intensity measure
ν
1
, and let P
2
be a draw
from a PPP with intensity measure
ν
2
, which has density f
2
with respect to
ν
1
.Then
the density of the distribution of P
2
with respect to P
1
is
f (p)=exp(
ν
1
(S) −
ν
2
(S))
∏
v∈p
f
2
(v). (7.1)
(See Proposition 3.8 of [105].) In particular, if
ν
1
is just Lebesgue measure, th is
expression gives the density of the PPP with respect to a standard PPP.
7.1 Acceptance/rejection
The simplest protocol for perfect simulation of spatial point processes is once again
acceptance/rejection. An AR-style algorithm operates in the same fashion as for dis-
crete problems. The ingredients consist of a target density f (possibly unnormalized),
density g (possibly unnormalized) from which it is possible to sample directly, and a
constant c such that for all configurations x, f (x)/[cg(x)] ≤ 1.
Then AR first draws a sample X from g. Accept the sample as a draw from f with
prob ability f (X)/[cg(X)]. Otherwise, r eject and start over.
To illustrate these ideas, consider the Strauss process. This is an example of a
repulsive process, which penalizes point processes every time a pair of points in the
process is closer than R to each other.
Definition 7.3. The Strauss process has a density with respect to a standard PPP.
There are three parameters of the model,
β
> 0,
γ
∈[0, 1], and R > 0. The density is
then
f (x)=
β
#x
γ
p
R
(x)
, (7.2)
where p
R
(x) is the number of pairs of points in x such that the distance between them
is at most R.
ACCEPTANCE/REJECTION 123
Acceptance/rejection for drawing from the Strauss process over a bounded win-
dow first begins by drawing a process with density
β
#x
against a standard PPP. This
part is easy: just generate a PPP (call it P) with constant intensity
λ
(x)=
β
through-
out using Definition 7.2 . Then
β
#x
γ
p
R
(x)
/
β
#x
≤1, so set c = 1. So accept P as a d raw
from the Strauss process with probability
γ
p
R
(P)
.
This works well if
γ
is close to 1. However, if
β
and S are large, and
γ
is small,
this will give an exponentially small chance of acceptance.
7.1.1 Covering points
Consider the following model with parameters
λ
and R greater than 0, and a special
point v ∈S. The goal is to draw a spatial point process of rate
λ
such that there exists
at least one point in the process that lies within distance R of v.LetB(v,R) denote
the set of points within distance R of v ( also known as the ball of radius R around v).
Then the density of a configuration x is f
v
(x)=1(B(v,R) ∩x = /0).
Again basic AR can be used for this process. Repeatedly draw a PPP of rate
λ
until the draw contains a point within distance R of v.Ofcourse,if
λ
is small, this
might take a large number of draws in order to achieve the goal. The goal is to create
a method that works well even when
λ
is very small.
To understand the technique that solves this problem, consider the following two-
step procedure. Suppose that we have an algorithm to generate from f
v
.Firstdraw
P ∼ f
v
, then uniformly select one of the points of P ∩B(v, R) to receive a mark. Let
m denote the marked point. The proba bility that m is the marked point given P is
1/#(x ∩B(v,R)). Therefore, the density of the marked process is just f
v,mark
(x,m)=
[ f
v
(x)/#(x ∩B(v,R))]1(m ∈ x ∩B(v,R)).
At this point, we do not have a method for obtaining draws from f
v
, so we cannot
create a draw from f
v,mark
by first drawing P and then uniformly marking a point.
On the other hand, suppose that we could draw from f
v,mark
. Then, to draw from f
v
,
first draw from f
v,mark
and then just throw away the mark at m leaving x. Since there
are #(x ∩B(v,R)) possible points that could have been marked, each with density
f
v
(x)/#(x ∩B(v, R)), summing gives that the density of the result of this procedure is
f
v
. So the problem of simulating from f
v
has been reduced to drawing from f
v,mark
.
Drawing from f
v,mark
can be accomplished using AR. First draw from
g
mark
(x,m)=1(m ∈ x ∩B(v, R)). This can be done by drawing the marked point
m first uniformly from B(v,R). Conditioned on this point being in the point process
P, the rest of P can be found by simply drawing a point process from S and taking
the union with m.
This gives a draw P from g
mark
(x,m). Accept P as a draw from f
v,mark
with prob-
ability f
v,mark
(x)/g
vmark
= 1/#(x ∩B(v, R)).When
λ
is small, #(x ∩B(v,R)) is likely
to be 1 and so the algorithm will take only a small number of draws.
So AR for f
v
works well when
λ
is large, and f
v,mark
works well when
λ
is small.
The interruptibility of AR can be used to combine the two to get an algorithm that
works well whether
λ
is large or small.
124 SPATIAL POINT PROCESSES
Covering PPP
Input: S, v, R Output: Poisson point process {X
1
,...,X
N
}∼f
v
1) cflag ← FALSE
2) Let
μ
be the product of
λ
and the Lebesgue measure of S
3) Repeat
4) Draw N as a Poisson random variable with mean
μ
5) Draw X
1
,...,X
N
iid uniformly from S
6) If B(v, R) ∩{X
1
,...,X
N
} = /0, then cflag ← TRUE
7) Else
8) Draw N as a Poisson random variable with mean
μ
9) Draw X
1
,...,X
N
iid uniformly from S
10) Draw X
N+1
← Unif(B(v,R)), N ← N + 1
11) Draw U ← Unif([0,1])
12) cflag ←U ≤ 1/#(B(v, r ) ∩{X
1
,...,X
N
})
13) Until cflag
Lemma 7.2. The expected number of random variables generated by Covering PPP
is at most (2 +
μ
)(1 + 2/
√
3).
Proof. Let P be a Poisson process drawn from S. Then to generate P requires gener-
ating N with mean
μ
, and then generating N points. So on average this takes 1 +
μ
points. Lines 8 through 12 require one more draw (for X
N+1
), so take 2 +
μ
points on
average.
Let p be the probability that such a draw P has B(v, R) ∩P = /0. Note that lines 8
through 12 only happen with probability 1 − p, and then only fail with probability at
most p. Hence, if T is the number of random variables drawn by the algorithm
E[T ] ≤ 1 +
μ
+(1 − p)[2 +
μ
+ pE[T ]], (7.3)
so E[T ] ≤ (2 +
μ
)(2 −p)/(1 −p + p
2
) ≤ (2 +
μ
)(1 + 2/
√
3).
7.2 Thinning
The simulation view of a PPP was used in the previous section. A different view
concentrates on the expected number of points that fall into any bounded region.
Lemma 7.3. For any bounded set A ⊆ S , and P a Poisson point process of rate
λ
over S, E[#(A ∩P)] =
A
λ
(x) dx.
Proof. This follows immediately from the simulation description.
Lemma 7.4. Let A and B be any two nonoverlapping measurable subsets of S. Then
for P a PPP of rate
λ
over S, P ∩A and P ∩B are independent.
Proof. Again this follows directly from the simulation definition.
THINNING 125
What is perhaps surprising is that these properties actually characterize a Poisson
point process (a fact that will be used here without proof). They also lead directly to
the notion of thinning.
Suppose that P is a Poisson point process of rate
λ
. For each point x in P,in-
dependently flip a coin with probability p (x) of heads. Let P
be the point process
consisting of points of P that received a head.
Then if P ∩A and P∩B are independent, so are P
∩A and P
∩B. Informally, for a
measurable set A, because each point in P ∩A is only retained for P
with probability
p(x), the expected number of points in P
is
A
λ
(x)p(x) dx. That means that P
satisfies the two conditions of being a Poisson point process over S of rate
λ
p.These
ideas can be summarized as follows.
Definition 7.4. Suppose for a PPP P, each point X ∈P has an independent Bernoulli
B
X
with mean
α
(X).ThenQ= {X ∈ P : B
X
= 1} forms the thinned point process.
Theorem 7.1. Let P be a PPP of intensity
λ
, and Q is thinned from P using function
α
. Then Q is also a PPP of intensity
αλ
.
See [105, p. 23] for a formal proof.
A thinned process can be used to build a perfect simulation algorithm when the
intensity
λ
is given by a density f
λ
with respect to Lebesgue measure that is uni-
formly bounded above by M over the space S.
Bounded PPP
Input: S, f
λ
, M Output: Poisson point process P
1) Let
μ
be M times the Lebesgue measure o f S
2) Draw N as a Poisson random variable with mean
μ
3) Draw X
1
,...,X
N
iid uniformly from S
4) For each x ∈{X
1
,...,X
N
}
5) Draw U ← Unif([0,1])
6) If U > f
λ
(x)/M,thenP ← P {x}
The expected running time of the algorithm is proportional to the Lebesgue mea-
sure of S times M, and so it is important to get as tight a bound on f
λ
as possible.
7.2.1 Example: a normal-intensity PPP
For example, suppose the goal is to generate a Poisson point process on the one-
dimensional interval from 0 to 1, subject to intensity
λ
(x)=(2
π
)
−1
exp(−x
2
/2).
This intensity has maximum value (2
π
)
−1
at x = 0. So first generate a Poisson point
process of intensity (2
π
)
−1
over the interval [0,1]. Then, for each point in the process,
accept the point as coming from the desired process with probability exp(−x
2
/2).
The r esult will have the target den sity.
7.2.2 Using thinning to make the window easier
Thinning can also be used to simplify the window over which sampling occurs. Sup-
pose that the goal is to generate a Poisson process o f r ate
λ
over an unusual bounded
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.