136 SPATIAL POINT PROCESSES
1. Since M is in fact random, it is necessary to integrate over all values of the mark
to get:
p(x)=1 −
m≥0
exp(−mK(x,W )) dM(m)=1 −L
M
(K(x,W )), (7.11)
where L
M
is the Laplace transform of the mark distribution M.
We only care about a parent point if it has a daughter point that falls into W .
Otherwise, the parent point might as well be deleted. So in a sense, all the points
in the parent process are being thinned based on their location. The chance that the
point is retain ed is p(x). Given that a parent point is retained, then choose a number of
daughter points to fall in W conditional on at least one point in the daughter process
falling in W .
So how can such a process be realized? The steps are as follows.
1. First create an upper bounding density
λ
u
(x) ≥ p(x) and
S
λ
u
(x) dR
2
< ∞.
2. Generate a PPP X from S with density
λ
.
3. For each point X, r etain X with probability p(x)/
λ
(x).
7.6.1 Example: Gaussian daughters
As an example of how this method can be carried out in practice, consider a window
W ,whichis[−1,1]
2
. The parent process h as constant density
λ
(·)=
λ
. Each point
in the parent p rocess h as mark value M = 1. Also, each point has a daughter process
whose intensity is a standard bivariate Gaussian, so that
k(x,w)=
1
2
π
exp
−
1
2
w −x
2
.
In order to use the method from Section 7.6, it is n ecessary to give an upper
bound on k(x,w) that integrates to a finite value over the plane. Note that for w ∈W ,
w≤
√
2. So from the triangle inequality, w −x≥x−
√
2. If x≥2
√
2, then
w −x≥x/2andw −x
2
≥x/4. If x< 2, then w −x
2
≥ 0.
Hence
k(x,w) ≤
1
2
π
exp
−
1
2
x
2
4
1(x≥2
√
2)+1(x < 2
√
2)
.
Using 1(x< 2
√
2)/(2
π
) ≤ exp(−1) gives
k(x,w) ≤ exp
−
1
2
x
2
4
,
and so setting
λ
(x)=exp(−x
2
/8) gives us the upper bound on the density.
Since
λ
(x) integrates to 8
π
over R
2
,onaverage8
π
points will be drawn in the
upper bounding process. Once the location of each point x is drawn, it is easy to
compute L k(x,W ) and so p (x). Accept each point as being a daughter spawning
CONTINUOUS-TIME MARKOV CHAINS 137
point with probability p(x)/
λ
(x). Finally, for each accepted point, draw a Poisson
random variable with mean L k(x,W ), and draw this many daughter points for the
window according to k(x,·).
The resulting union of daughters of these thinned parent points is the draw from
the cluster process for the observed window.
Møller and Rasmussen [102] later extended this method to Hawkes processes
where each daughter point can itself be the parent for a new point, which can in turn
be a parent to daughter points, and so on indefinitely.
7.7 Continuous-time Markov chains
Recall that jump p rocesses are also known as continuous-time Markov chains.These
types of Markovian processes arise in many models, especially in queues.
7.7.1 Monotonic CFTP for Jackson queuing networks
Definition 7.8. A queue consists of a set of customers waiting in line to be served.
When a customer arrives, the length of the queue increases by 1. When a customer is
served (which can only happen when the queue length is positive), the queue length
decreases b y 1.
Definition 7.9. When the customers arrive to the queue according to a Poisson pro-
cess with fixed rate
λ
, there is a single server who serves customers one at a time,
and the service time is exponentially distributed with rate
μ
,thenitisanM/M/1
queue. (The first M means that the arrivals are memoryless, the second M means the
services are memoryless, and the 1 indicates that there is a single server.)
This basic notion of queues allows for the length of queue to be arbitrarily large,
but most q ueues in practice have a limit on their size.
Definition 7.10. A capacitated queue has a capacity C for the queue. If there is an
arrival to the queue when the length is already C, the arrival is turned away and
disappears. An M/M/1 queue with capacity C is denoted as M/M/1/C. If the queue
has infinite capacity it is denoted M/M/1/∞.
M/M/1/C queues form a finite-state continuous-time Markov chain, and have
been well studied. The stationary distribution is simple and easy to simulate from.
Things become more interesting when once a customer leaves the queue, that cus-
tomer might enter into another queue.
Definition 7.11. A Jackson network consists of a set of nodes V where once a cus-
tomer is served at node i, it joins the queue at node j with probability p
ij
. With
probability 1 −
∑
j=i
p
ij
, it leaves the system. The service rate
λ
i
is constant for each
node i. The network is open if there is an arrival process of rate
λ
, where each arrival
goes to queue i with probability p
0i
, and
∑
i
p
0i
= 1.
If each queue in the Jackson network has arrivals and services that are exponen-
tially distributed, then the Jackson network will be a continuous-time Markov chain.
When the capacity of all the queues is infinite, th e statio nary distribution has a well-
138 SPATIAL POINT PROCESSES
known product form, but when the capacities are finite this form becomes d ifficult to
compute.
Monotone CFTP was first applied to this problem by Mattson [90]. Events con-
sist of one of two types: arrival to a queue, and service from a queue. Since the
arrival and service processes are Poisson, each can be considered separately. Recall
the following well-known fact about exponential random variables.
Lemma 7.7. Let X
1
,...,X
n
be independent exponentially distributed random vari-
ables, with X
i
∼Exp(
λ
i
).LetY∼ Exp(
∑
i
λ
i
).ThenY∼ min{X
1
,...,X
n
} and P (X
i
=
min{X
1
,...,X
n
})=
λ
i
/(
∑
j
λ
j
).
The number of events that occurs in an interval [t
1
,t
2
] will be the length of the
interval, t
2
−t
1
, times the rate at which events occu r. In a Jackson n etwork, the total
rate of events is
λ
+
∑
i
λ
i
. This allows the building of a set of service an d arrival
times over an interval. In the following pseudocode, a positive integer value at a(t)
indicates that there was an arrival at node a(t), while an ordered pair (i, j) in the list
indicates that there was an attempted service at node i, and af ter the service (if it took
place) the customer moved to the queue at node j. If the pair is of the form (i,0) then
the customer left the queue after service.
Jackson network event list Input: t
1
< t
2
Output: event list a
1) Draw N ← Pois((t
2
−t
1
)[
λ
+
λ
i
])
2) Let a be an empty list
3) For t from 1 to N do
4) Draw X ← Bern(
λ
/[
λ
+
∑
i
λ
i
])
5) If (X = 1) then (there is an arrival event)
6) Draw I so that P(I = i)=p
0i
7) Append I to a
8) Else (there is a service)
9) Draw I so that P(I = i)=
λ
i
/[
∑
i
λ
j
]
10) Draw J so that P(J = j)=p
ij
, P(J = 0)=1 −
∑
k
p
ik
11) Append (I, J) to list a
For example, if for interval [−5,0] the output was a =(3,(2,1),2), that means
that during the time from −5 up to 0, there was an arrival to node 3 followed by a
service at node 2 that then moved to queue 1, and an arrival at node 2.
To actually update the state of the Jackson network, use the events provided to
change the values at each queue. Let (C
1
,...,C
m
) be the capacities of the m queues
in the network.
Jackson network update Input: x, a Output: x
1) For t from 1 to the number of events in a do
2) If a(t)=i for some node i
3) x(i) ← x (i)+1(x(i) < C
i
)
4) Else a(t)=(i, j)
5) x( j) ← x( j)+1(x(i) > 0)1(x( j) < C
j
)
6) x(i) ← x (i) −1(x(i) > 0)
CONTINUOUS-TIME MARKOV CHAINS 139
It is straightforward to check that for any pair of vectors x ≤y and any event list a,
it holds that Jackson
network update(x,a) ≤ Jackson network update(y, a).
Therefore it can be used to run monotone CFTP using the minimal state of all 0’s
and the maximal state of (C
1
,...,C
m
).
Jackson network mcftp Input: t Output: x
1) a ← Jackson network event list(t)
2) x
min
← (0,0,...,0), x
max
← (C
1
,...,C
m
)
3) x
min
← Jackson network update(x
min
,a)
4) x
max
← Jackson network update(x
max
,a)
5) If x
min
= x
max
6) x ← x
min
7) Else x ← Jackson network mcftp(2t)
8) x ← Jackson
network update(x, a)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset