Transcript Document

The Poisson Process
Definition
What is A Poisson Process?
The Poisson Process is a counting that counts the number
of occurrences of some specific event through time
Examples:
- Number of customers arriving to a counter
- Number of calls received at a telephone exchange
- Number of packets entering a queue
© Tallal Elshabrawy
2
The Poisson Process
1st Event
Occurs
X1
t=0




2nd Event
Occurs
S1   Xi
i1
2
S 2   Xi
i 1
4th Event
Occurs
X4
X3
X2
1
3rd Event
Occurs
3
S3   Xi
i 1
4
time
S 4   Xi
i 1
X1, X2, … represent a sequence of +ve independent random
variables with identical distribution
Xn depicts the time elapsed between the (n-1)th event and nth event
occurrences
Sn depicts a random variable for the time at which the nth event
occurs
Define N(t) as the number of events that have occurred up to some
arbitrary time t.
The counting process { N(t), t>0 } is called a Poisson process if the
inter-occurrence times X1, X2, … follow the exponential distribution
© Tallal Elshabrawy
3
The Poisson Process: Example
For some reason, you decide everyday at 3:00 PM to
go to the bus stop and count the number of buses
that arrive. You record the number of buses that
have passed after 10 minutes
N (t=10 min) = 2
Sunday
1st Bus
Arrival
X1=5 min
2nd Bus
Arrival
X2=4 min
3rd Bus
Arrival
X3=7 min
4th Bus
Arrival
X4=2 min
time
t=0
© Tallal Elshabrawy
S1 = 5 min
S2 = 9 min
S3 = 16 min
S4 = 18 min
4
The Poisson Process: Example
For some reason, you decide everyday at 3:00 PM to
go to the bus stop and count the number of buses
that arrive. You record the number of buses that
have passed after 10 minutes
N (t=10 min) =4
Monday
1st Bus
Arrival
2nd Bus
Arrival
X1=1 min X2=2 min
3rd Bus
Arrival
X3=4 min
4th Bus
Arrival
X4=2 min
5th Bus
Arrival
X5=6 min
time
t=0
S1 = 1 min S2 = 3 min
© Tallal Elshabrawy
S3 = 7 min
S4 = 9 min
S5 = 15 min
5
The Poisson Process: Example
For some reason, you decide everyday at 3:00 PM to
go to the bus stop and count the number of buses
that arrive. You record the number of buses that
have passed after 10 minutes
Tuesday
N (t=10 min) =1
1st Bus
Arrival
X1=10 min
2nd Bus
Arrival
X2=6 min
time
t=0
© Tallal Elshabrawy
S1 = 10 min
S2 = 16 min
6
The Poisson Process: Example
Given that Xi follow an exponential distribution then
N(t=10) follows a Poisson Distribution
© Tallal Elshabrawy
7
The Exponential Distribution
The exponential distribution describes a continuous
random variable
Cumulative Distribution Function (CDF)
FXn  x   Pr Xn  x  1  e
 λx
1
0
Probability Density Function (PDF)
fXn  x  
© Tallal Elshabrawy
dFXn  x 
dx
λ
 λe  λx
0
8
Mean of the Exponential Distribution


0
0
E X n    xfXn  x  dx   λxe  λx dx
Let u  x, dv  λe λx dx  du  dx , v  e λx
E X n   uv

0

  vdu   xe  λx
0

 1  λx
E X n     0   e

 λ

0

0

  e  λx dx
0
L ' Hopital Theorem
Limx 
x
1
 Limx 
0
λx
e
λe λx
1 1

E X n   0   
λ λ

© Tallal Elshabrawy
9
Variance of the Exponential Distribution


E  X    x fXn  x  dx   λx 2 e  λx dx
2
n
2
0
0
Let u  x 2 , dv  λe λx dx  du  2xdx, v  e λx
E  X n2   uv

0

  vdu   x 2 e  λx
0


 2
2
E  X n     0    xλe  λx dx

 λ0
2
2
E  Xn2   E Xn   2
λ
λ

0

 2 xe  λx dx
0
L ' Hopital Theorem
Limx 
x 2
0
e λx
2 1
1
2
2


Var Xn   E  Xn   E Xn   2  2  2
λ
λ
λ
© Tallal Elshabrawy
10
Laplace Transform of Exponential PDF
The Laplace transform of any PDF for a continuous
random variable may be used to deduce different
parameters and characteristics of the distribution




0
0
F  S   L fXn  x    fXn  x  e Sx dS  F  S    λe  λx e Sx dS 
λ
Sλ
What could F(S) be used for
E Xn   
E  Xn2  
© Tallal Elshabrawy
dF  S 
dS
S 0
d2F  S 
dS
2
S 0

λ
S  λ 
2

S 0
1

λ
d
2

λ S  λ 
dS

S 0

λ  2 S  λ 
S  λ 
4
S 0
2
 2
λ
11
Probability Density Function for Sk
k
Sk   Xi
i1
The probability density function for the sum of k
independent random variables (X1, X2, …, Xk) could be
deduced from the Laplace transform of fXn(x) as follows

fSk  t   L1 fXn  x 
k

k


λ




1
 L 
 
S

λ
 



From Laplace Transform Tables
t k 1
fSk  t   λ
e  λt
 k  1 !
k
© Tallal Elshabrawy
12
Cumulative Distribution Function for Sk
k
Sk   Xi
i1
k


1
1
λ






1
1
FSk  t    fSk  x dx  L  L fSk  x    L  
 
S
S
S

λ


 
0

 

t


From Laplace Transform Tables
k 1
FSk  t   Pr Sk  t   1   e
i0
© Tallal Elshabrawy
 λt 
i
 λt
i!
13
The Poisson Distribution
Pr N t   k   Pr Sk  t 
Pr N  t   k  1  Pr Sk 1  t 
Pr N t   k   Pr N  t   k   Pr N  t   k  1
i
i
k 1
k

 

λ
t
λ
t




 λt
 λt
  1   e

Pr N  t   k   1   e
i!  
i! 

i0
i0
 

Pr N  t   k   e  λt
© Tallal Elshabrawy
 λt 
k
k!
Probability Mass Function for
the Poisson Distribution
14
Mean of the Poisson Distribution


k 0
k 0
E N  t     k Pr N  t   k    ke
E N  t   e
 λt
E N  t    e
 λt
 λt 
k
 λt
k!

  ke
 λt 
k
 λt
k 1
k!
λt 

 λt  
k 1  k  1 !
k 1


 λt  
k 0
 λt 
k
K!
  λt 
yk
e y

k 0 k !

where
On average the time between two consecutive events is 1/λ
This means that the event occurrence rate is λ
Consequently in time t, the expected number of events is λt
© Tallal Elshabrawy
15
Variance of the Poisson Distribution


2
E N  t     k 2 Pr N  t   k    k 2 e  λt

 k 0
k 0
 λt 
k
k!

 k e
k 1
2
 λt 
k
 λt
k!
λt 

2
 λt


E N  t   e  λt   k  1  1


 k  1 !
k 1

2
E N  t  


2

E Nt  


k 1
k 1
k 1


λt 
λt  


 λt

 e  λt     k  1

k  1 ! k 1 k  1 !
 k 1
k 2
k 1



λt 
λt  


 λt

 e  λt   λt  


k 2 k  2  !
k 1  k  1  ! 

2
2
E N  t    e  λt  λt   λt  e λt  e λt    λt    λt   Var N  t     λt 


© Tallal Elshabrawy
16
Moment Generating Function of Poisson Distribution
The Moment Generating Function of any PMF for a
discrete random variable may be used to deduce
different parameters and characteristics of the distribution


k 0
k 0
G  Z   E ZN    Zk Pr N  k   
λt 
k  λt 
Z e
k
k!

e  λt 
k 0
 Zλt 
k
k!
e
 λt 1 Z 
What could G(Z) be used for
E N  t   
dG  Z 
E N  t   


2
© Tallal Elshabrawy
dZ
Z 1
  λt  e
d2 G  Z 
dZ 2
Z 1

 λt 1  Z 
dG  Z 
dZ
Z 1
  λt 
  λ t    λt 
2
Z 1
17
Remaining Time of Exponential Distributions
Xk+1 is the time interval between
the kth and k+1th arrivals
kth Event
Occurs
T
Condition:
T units have passed and the
k+1th event has not occurred yet
Question:
X*
X*k+1
k
Sk   Xi
Given that k+1 is the remaining
time until the k+1th event
occurs
What* is Pr[X*k+1≤x]
Pr  X k 1  x   Pr  X k 1  T  x X k 1  T 
Pr  T  X k 1  T  x 
*
Pr  X k 1  x  
Pr  X k 1  T 
Pr  X k 1  T  x   Pr  X k 1  T 
*
Pr  X k 1  x  
1  Pr  X k 1  T 
© Tallal Elshabrawy
k+1th Event
Occurs
i1
18
Remaining Time of Exponential Distributions
Pr  X
*
k 1
Pr  X k 1  T  x   Pr  X k 1  T 
 x  
1  Pr  X k 1  T 
Xk+1 follows an exponential Distribution, i.e.,
Pr[Xk+1≤t]=1-e-λt
Pr  X *k 1
1e

 x 
  1  e   
1  1  e   

Pr  X *k 1  x  
e
λ T
λ T  x
λ T
λ T
e
e
λ T x
λ T
1 e
λx
The remaining time X*k+1 follows an exponential distribution with the
same mean 1/λ as that of the inter-arrival time Xk+1
© Tallal Elshabrawy
19
The Memoryless Property of Exponential Distributions
The Memoryless Property:
The waiting time until the next arrival has the same
exponential distribution as the original inter-arrival time
regardless of long ago the last arrival occurred
Memoryless Property of Exponential Distribution and the
Poisson Process
Pr N  u  s   N  u   k  
 λs
λs
e
 
k
k!
In the Poisson process, the number of arrivals within any
time interval s follows a Poisson distribution with mean λs
© Tallal Elshabrawy
20
Merging of Poisson Processes
 {N1(t), t ≥ 0} and {N2(t), t ≥ 0} are two independent Poisson
processes with respective rates λ1 and λ2,
 {Ni (t)} corresponds to type i arrivals.
 The merged process N(t) = N1(t) + N2(t), t ≥ 0. Then {N(t),
t ≥ 0} is a Poisson process with rate λ = λ1 + λ2.
 Zk is the inter-arrival time between the (k − 1)th and kth
arrival in the merged process
 Ik= i if the kth arrival in the merged process is a type i
arrival,
 For any k = 1, 2, . . . ,
P{Ik = i | Zk = t} =λi/(λ1+λ2) , i= 1, 2, independently of t .
© Tallal Elshabrawy
21
Splitting of Poisson Processes
 {N(t), t ≥ 0} is a Poisson process with rate λ.
 Each arrival of the process is classified as being a type 1
arrival or type 2 arrival with respective probabilities p1 and
p2, independently of all other arrivals.
 Ni (t) is the number of type i arrivals up to time t .
 {N1(t)} and {N2(t)} are two independent Poisson processes
having respective rates λp1 and λp2.
© Tallal Elshabrawy
22