1

IEDA4130 System Simulation

7. Poisson Process

Nian Si
HKUST
 2

Announcement
Homework 3 will be released today. It is about lecture 6 variance
reduction and this lecture. It is due on Wednesday, Apr. 9th.
POISSON PROCESS 3

Poisson Process
1 Introduction

2 Simulating Poisson Process

2.1 Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . .

3 Nonhomogeneous Poisson Process

3.1 Simulating Piecewise Constant Poisson Process . . . . .
3.2 Simulating Nonhomogeneous Poisson Process by the
Thining Algorithm . . . . . . . . . . . . . . . . . . . . .

4 Compound Poisson Process

1 INTRODUCTION 4

1 Introduction
ˆ Used to describe occurrences of unpredictable events, but which
also have some statistical regularity
– Times at which customers are at a store
– Times at which patients are at a store
– Moments at which a certain place is hit by an earthquake

Example: A Call Center

Imagine you’re running a call center. Calls come in randomly. You don’t
know exactly when the next call will happen, but you do know that, on
average, you get about 10 calls per hour. This randomness, but with a
predictable average rate, is exactly what the Poisson process models.
1 INTRODUCTION 5

Properties of Poisson processes

ˆ Let’s say the process happens at rate λ = 10 per hour. This means:
– In any small time interval, there’s a small chance of getting a
call.
– The longer you wait, the more likely a call comes.
– On average, each hour will receive 10 calls.
ˆ Independence:
– Calls come in independently—knowing that a call just happened
doesn’t affect when the next one will come.
– The number of calls received during 9:00-10:00 is independent
to the number of calls received during 10:00-11:00.
ˆ Memoryless Interarrival Times: No matter how long you’ve been
waiting for the next call, the probability of it happening in the next
minute is the same as it was before.
1 INTRODUCTION 6

ˆ Poisson Random Variable: If a random variable follows the

Poisson distribution with parameter λ, then,
n
−λ λ
P(N = n) = e
n!
ˆ Possion process as a counting process: We count how many events
have occurred by time t.
– Denote N (t) to be number of arrivals up to time t.
– Then N (t) ∼ P oi(λt).
– For t > s, N (t) − N (s) ∼ P oi(λ(t − s)).
1 INTRODUCTION 7

Poisson Process
Suppose that ”events” are occurring at random time points, for
example, the arrival of customers at a store, and let {N (t), t ≥ 0}
denote the number of events that occur in the time interval [0, t] (the
number of customers at a store in the time interval [0, t]). These
events are said to constitute a Poisson process having rate λ, λ > 0 if
(a) N (0) = 0;
– states that the process begins at time 0.
(b) Stationarity: for any t > s ≥ 0, r ≥ 0, N (t) − N (s) and
N (t + r) − N (s + r) have the same distribution;
– states that the probability distribution of N (t + s) − N (t) is
the same for all values of t.
– examining the call times at a call center over a period of one
day or counting the number of customers in a store at one
day
1 INTRODUCTION 8

(c) Independence increment: for any t0 < t1 < · · · < tn , the random
variable N (t1 ) − N (t0 ), N (t2 ) − N (t1 ), . . . , N (tn ) − N (tn−1 ) are
independent;
– states that the number of events by time t, N (t) is independent of
the number of events that occur between t and t + s (i.e.
N (t + s) − N (t))
– e.g. the fact that a call takes place at say 9:20am says nothing about
the the probability of a call at a later time
P(N (h)=1)
(d) limh→0 h
= λ;
– states that in a small interval of length h, the probability of one
event occurring is approximately λh
P(N (h)≥2)
(e) limh→0 h
=0
– states that it is unlikely to have more than two events in an
arbitrarily small time interval h
1 INTRODUCTION 9

ˆ The r.v N (t) are related across time

N(t)

0 t

ˆ Ai is the time of the ith occurrence

ˆ Then N (t) = max{i : Ai ≤ t}
ˆ Both {N (t) : t ≥ 0} and {Ai : i = 1, 2, . . . } can be used to describe a
Poisson process
2 SIMULATING POISSON PROCESS 10

2 Simulating Poisson Process

ˆ Property 1: N (t) is a Poisson random variable with mean λt, t ≥ 0
ˆ Justification: by (d) and (e) over a very small time interval [0, h]:
– P(N (h) = 1) = λh
– P(N (h) ≥ 2) ≈ 0 (small compared to P(N (h) = 1))
– P(N (h) = 0) ≈ 1 − λh
– Number of occurrences in [0, h] is approximately Bern(λh)

ˆ Number of occurrences in [h, 2h] is N (2h) − N (h)

– By (a) and (c) N (2h) − N (h) and N (h) are i.i.d

ˆ Total number of occurrences in [0, t] is approximately Bin(t/h, λh)

ˆ We can show that Bin(t/h, λh) is approximately
P oi(t/h · λh) = P oi(λt) as h → 0
2 SIMULATING POISSON PROCESS 11

Algorithm 0 (not an exact simulation, and may be slow)

1. Discretization: We split the time [0, T ] into intervals of length ∆t.

2. Bernoulli Trials: Each interval gets one Bernoulli trial. The chance of
success (an arrival) is p = λ∆t.

3. Approximate Poisson: When ∆t is very small, this discrete process will

match the continuous-time Poisson process well.

Remarks:

ˆ Make sure λ∆t is much less than 1 to get a good approximation.

ˆ Decreasing ∆t will make the simulation slower but more accurate.
2 SIMULATING POISSON PROCESS 12

2.1 Algorithm 1
ˆ On top of the times of occurrences A1 , A2 , . . . , we can also define
inter-arrival times

ˆ Xi = Ai − Ai−1 are the inter-arrival times

N(t)

0 t
2 SIMULATING POISSON PROCESS 13

ˆ Property 2: X1 ∼ Exp(λ)
– Proof: consider P(X1 > t), t > 0
– P(X1 > t) = P(A1 > t) = P(N (t) = 0) = e−λx
– So P(X1 ≤ t) = 1 − P(X1 > t) = 1 − e−λt is the cdf of Exp(λ)

ˆ Let’s just show that X1 and X2 are independent

ˆ Consider P(X2 > t | X1 = s)
ˆ Have

P(X2 > t | X1 = s) = P(N (t + s) − N (s) = 0 | N (s) = 1)

= P(N (t + s) − N (s) = 0) = e−λt

ˆ RHS expression does not involve s

ˆ X1 and X2 independent; X2 ∼ Exp(λ)
ˆ Repeat argument for X3 , X4 , . . .
2 SIMULATING POISSON PROCESS 14

ˆ Property 2 is useful for simulating Poisson processes

ˆ Recall we define Poisson process through the N (t), t ≥ 0
ˆ Generating a Poisson process means generating the N (t)
ˆ In practice, only generate N (t) for [0, T ] (a finite interval)
ˆ Recall also
N (t) = max{ i : Ai ≤ t} = max{i | X1 + X2 + · · · + Xi ≤ t}

ˆ We can then use Property 2 and the relation above to generate a Poisson
process over a finite time interval
2 SIMULATING POISSON PROCESS 15

ˆ To generate {N (t) : t ∈ [0, T ]}

i.i.d
– Generate Xi ∼ Exp(λ) until we see X1 + X2 + · · · + Xn+1 > T
– Arrival times Ai = X1 + X2 + · · · + Xi , i = 1, 2, . . . , n

Algorithm 1: Simulate Poisson pocess by generating exponential

interarrival time

Step 1 t = 0, I = 0
Step 2 Generate X ∼ Exp(λ)
Step 3 t = t + X. If t > T , stop; else go to step 4
Step 4 I = I + 1, AI = t
Step 5 Go to Step 2.
Step 6 Output I, Ai , i = 1, 2, . . . , I.
2 SIMULATING POISSON PROCESS 16

2.2 Algorithm 2
ˆ Property 3: The conditional distribution (A1 , A2 , . . . , An | N (t) = n)
has the same distribution as the order statistics (U(1) , U(2) , . . . , U(n) ) of
i.i.d
(U1 , U2 , . . . , Un ) ∼ U nif orm(0, t)

ˆ Order statistics (U(1) , U(2) , . . . , U(n) ) of

i.i.d
(U1 , U2 , . . . , Un ) ∼ U nif orm(0, t) simply sorts the values of
U1 , U2 , . . . , Un in an increasing order
– E.g., n = 3, U1 = 1.5, U2 = 0.4 and U3 = 1.8 then ,
– Consider the density function
2 SIMULATING POISSON PROCESS 17

f (t1 , t2 , . . . , tn ) = P(A1 = t1 , A2 = t2 , . . . , An = tn | N (t) = n)

P(A1 = t1 , A2 = t2 , . . . , An = tn , N (t) = n)
f (t1 , t2 , . . . , tn ) =
P(N (t) = n)
P(X − 1 = t1 , . . . , Xn = tn − tn−1 , Xn+1 > t − tn )
=
P(N (t) = n)
(λe−λt1 )(λe−λt1 ) . . . , (λe−λtn )(e−λ(t−tn ) )
=
e−λt (λt)n /n!
n!
= n
t
2 SIMULATING POISSON PROCESS 18

ˆ Property 3 can be used to generate a Poisson process in another way

ˆ To generate a Poisson process with rate λ over [0, T ]

Algorithm 2: Simulate Poisson process by first generating a

Possion random variable then uniform random variables

Step 1 Generate N (T ) ∼ P oi(λT )

Step 2 Suppose N (t) = n. Generate n i.i.d U nif orm(0, T )
random variable U1 , U2 , . . . , Un
Step 3 Sort U1 , U2 , . . . , Un in an increasing order to get U(1) <
U(2) < · · · < U(n)
Step 4 Output n and Ai = U(i) , i = 1, 2, . . . , n
2 SIMULATING POISSON PROCESS 19

ˆ We now know that N (t) ∼ P oiss(λt)

ˆ Also Xi ∼ Exp(λ)
ˆ What about Ai ?
(λt)2 (λt)n−1
ˆ P(An > t) = P(N (t) < n) = e−λt (1 + λt + 2!
) + ··· + (n−1)!

ˆ P(An > t) = 1 − Fn (t), where Fn (t) is the CDF of An

ˆ Differentiation gives
−λt λn tn−1
fn (t) = e
(n − 1)!
where fn is the pdf of An
3 NONHOMOGENEOUS POISSON PROCESS 20

3 Nonhomogeneous Poisson Process

A nonhomogeneous (or inhomogeneous) Poisson process is just like a
standard Poisson process—except the rate of arrivals changes over time
instead of staying constant. A good intuitive real-life example is customers at
a coffee shop in a workday:

ˆ Morning rush (8–10 AM): The arrival rate is high because lots of
people grab coffee on their way to work.

ˆ Morning (10AM–12 PM): Morning Working time: the arrival rate slows
down as fewer people come in.

ˆ Noon (12–2 PM): The arrival rate increases at the lunch time.
ˆ Afternoon (2–6 PM): The rate decreases again in the afternoon
working time.
3 NONHOMOGENEOUS POISSON PROCESS 21

(a) Arrival rates (b) Arrivals

Figure 3.1: Arrival plots at the coffee shop.

3 NONHOMOGENEOUS POISSON PROCESS 22

Definition of Nonhomogeneous Poisson Process

We say that {N (t) : t ≥ 0} is a nonhomogeneous process with rate
{λ (t) : t ≥ 0} (for λ (t) ≥ 0) if

1. N (0) = 0,

2. For any 0 ≤ t0 < t1 < .... < tm , the random variables

N (t1 ) − N (t0 ) , ..., N (tm ) − N (tm−1 )

are independent.

3. For any 0 ≤ s < t we have

Z t 
N (t) − N (s) ∼ P oisson λ (r) dr .
s

(that is the NUMBER of arrivals in the interval [s, t] is distributed

Poisson with rate equal to the integral of the intensity in the interval
[s, t]).
3 NONHOMOGENEOUS POISSON PROCESS 23

Suppose that ∆ > 0 is small. N (·) can be imagined as a process in which at

a given interval [t, t + ∆], an arrival comes with probability λ (t) ∆
independent from what happens in other intervals.

This is analogous to the case of a standard

Poisson process with constant intensity...
3 NONHOMOGENEOUS POISSON PROCESS 24

Algorithm 0 (not an exact simulation, and may be slow)

1. Discretization: We split the time [0, T ] into intervals of length ∆t.

2. Bernoulli Trials: Each interval gets one Bernoulli trial. The chance of
success (an arrival) is p = λ(t)∆t for the interval [t, t + ∆t].

3. Approximate Poisson: When ∆t is very small, this discrete process will

match the continuous-time Poisson process well.
3 NONHOMOGENEOUS POISSON PROCESS 25

3.1 Simulating Piecewise Constant Poisson

Process
Suppose that λ(t) = λi for t ∈ [ti−1 , ti ), where
0 = t0 < t1 < . . . < tK−1 < tK = T .

Algorithm 1

Step 0 I = 0.
for k = 1 to K
Step 1 t = tk−1
Step 2 Generate X ∼ Exp(λk )
Step 3 t = t + X. If t > tk , increment k; else go to step 4
Step 4 I = I + 1, AI = t
Step 5 Go to Step 2.
end for
Output I, Ai , i = 1, 2, . . . , I.
3 NONHOMOGENEOUS POISSON PROCESS 26

Algorithm 2: Simulate Poisson process by first generating a Possion

random variable then uniform random variables

Step 0 I = 0
for k = 1 to K
Step 1 Generate N (tk ) − N (tk−1 ) ∼ P oi(λ(tk − tk−1 ))
Step 2 Suppose N (tk ) − N (tk−1 ) = n. Generate n i.i.d
U nif orm(0, tk − tk−1 ) random variable U1 , U2 , . . . , Un
Step 3 Sort U1 , U2 , . . . , Un in an increasing order to get U(1) <
U(2) < · · · < U(n)
Step 4 Ai = tk−1 + U(i) , i = I + 1, I + 2, . . . , I + n
Step 5 I = I + n.
end for
Output I and Ai , i = 1, 2, . . . , I
3 NONHOMOGENEOUS POISSON PROCESS 27

3.2 Simulating Nonhomogeneous Poisson Process

by the Thining Algorithm
Suppose that λ(t) ≤ λmax , for all t ≤ T . Then we can develop a
acceptance/rejection-type method.
STEP 1: t = 0, I = 0.
STEP 2: Generate an expoential random variable X ∼ exp(λmax ) .
STEP 3: t = t + X. If t > T , stop.
STEP 4: Generate a uniform random number U .
STEP 5: If U ≤ λ(t)/λmax , set I = I + 1, S(I) = t.
STEP 6: Go to Step 2.
4 COMPOUND POISSON PROCESS 28

4 Compound Poisson Process

Example Customers at a coffee shop in a workday:

1. Customers Arrive (Poisson Process). Imagine customers entering a

coffee shop according to a (nonhomogenous) Poisson process.

2. Each Customer Makes a Random Purchase (Compounding). When a

customer arrives, the amount they spend is random. One customer
might just buy a small coffee for $2.50, while another could purchase
multiple items (e.g., coffee and pastries) for $10.00.

3. Total Revenue is the “Compound.” If we track how much money the

coffee shop makes over time, the total revenue combines: - How many
customers showed up (the Poisson part). - The random purchase amount
each customer made (the “compound” part).

Mathematically, if N (t) is the (Poisson) number of customers arriving up to

time t, and Xi is the purchase amount of the i-th customer, then the total
4 COMPOUND POISSON PROCESS 29

revenue S(t) is:

N (t)
X
S(t) = Xi .
i=1

Every time N (t) increases by 1 (a new customer arrives), S(t) jumps by the
random amount Xi of that customer’s purchase. This is precisely what
defines a compound Poisson process.

ˆ To simulate compound Poisson process, we only need to independently

simulate N (t) and {Xi }.