Poisson Process
Presented by : Johniel E. Babiera
Example 1
We are interested in the dynamics of the arrival of telephone calls to a call center.
To describe these arriving calls, consider a collection of random variables { ,
0}, where each random variable , for a fixed , denotes the cumulative number
calls coming into the center by time . Since calls record a count, the state space is
the set of whole number = {0,1,2, }.
Definition 1
Let the continuous parameter stochastic process { , 0} with 0 = 0 have a
state space equal to the nonnegative integers . It is called with
rate if
a) = =
for all nonnegative and 0.
b) The event {+ = } is independent of the event { = } if < .
c) {+ = } only depends on the value of .
Example 2
For example, if the process in example 1 has independent increments, then
knowledge of the number of calls that arrived before 11:00AM will not help in
predicting the number of calls to arrive between 11:00AM and noon. Likewise, if
the process has stationary increments, then the probability that k calls arrive
between 10:00AM and 10:15AM will be equal to the probability that k calls arrive
between 4:00PM and 4:15PM because the size of both intervals is the same. It
turns out that an arrival process with independent and stationary increments in
which arrivals can only occur one-at-a-time must be a Poisson process.
We have = . In others words, gives the mean arrival rate per unit time
for an arrival process that is described by a Poisson process with rate .
Because Poisson process has independent and stationary increments, we also
have, for nonnegative
+ = =
for 0.
!
Example 3
Assume that the arrivals to the call center described in can be modeled according
to a Poisson process with rate 25/. The number of calls that are expected
within an eight-hour shift is =8 = 25 8 = 200. Assume we had 20 calls
that arrived from 8AM through 9AM. What is the probability that there will be no
calls that arrive from 9:00AM through 9:06AM? Because of independent
increments, the information regarding the 20 calls is irrelevant. Because of
station stationary increments, we only need to know that the length of the
interval is 6 minutes (or 0.1 hours), note that it starts at 9AM; thus, the
answer is given as
0.1
25 0.1
=0 =
= 0.08208
!
Properties of Poisson Process
Property 1. A Poisson process with rate has exponentially distributed
inter-arrival times with the mean time between arrivals being 1/ . The
converse is also true; namely, an arrival process with exponentially
distributed inter-arrival times is a Poisson process.
Consider an interval of length t. The probability that no arrival occurs within that
interval is = 0 = . Let denote the time that the first arrival occurs.
The event { > } is equivalent to the event { = 0}; therefore,
0 = 1 > 0 = 1 for 0
which is the CDF for the exponential distribution.
Property 2. Let denote the arrival time for a Poisson process with
rate . The random variable has an Erlang distribution with pdf given
by
1
=
0 .
1 !
()~(, )
Property 3. Superposition of Poisson Processes: Let { ; 0} and
{ ; 0} be two independent Poisson process with rates 1 and 2 .
Form a third process by = + , for each 0. The process { ;
0} is a Poisson process with rate 1 + 2 .
Example 4 (property 3)
Consider the diagram in the right representing a
limited access highway. Assume that the times in
which cars pass Point A form a Poisson process
with rate 1 = 8/min and cars passing Point B
form a Poisson process with rate 2 = 2/min.
After these two streams of cars merge, the times at which cars pass
Point C form a Poisson process with mean rate 10/min.
Property 4. Decomposition of a Poisson Processes: Let = { ; 0} be a
Poisson process with rate and let {1 , 2 , } denote an i.i.d sequence of
Bernoulli random variables independent of the Poisson process such that
= 1 = . Let = { ; 0} be a new process formed as follows; for
each positive , consider the arrival to the process to also be an arrival to
the process if = 1; otherwise, the arrival to the process is not part of
the process. The resulting process is a Poisson process with rate .
Example 5 (property 4)
Consider traffic coming to a fork in the road, and assume that the arrival times of
cars to the fork form a Poisson process with mean rate 2 per minute. In addition,
there is a 30% chance that cars will turn left and a 70% chance that cars will turn
right. Under the assumption that all cars act independently, the arrival stream on
the left-hand fork form a Poisson process with rate 0.6/min and the stream on
the right-hand fork form a Poisson process with rate 1.4/min.
Queuing Theory
Queuing Theory
The study of waiting line phenomena (a queue is a waiting line)
The theory enables mathematical analysis of several related
processes, including arriving at the (back of the) queue, waiting in
the queue and being served at the front of the queue.
The theory permits the derivation and calculation of several
performance measures including the average waiting time in the
queue, the expected number waiting or receiving service, and the
probability of encountering the system in certain states, such as
empty, full, having an available server or having to wait a certain
time to be served.
Kendall Notation
General Form
(A/B/c/K/m/Z)
A
B
c
K
m
Z
- inter-arrival time distribution
- service time distribution
- the number of servers
- the system capacity (number of customer)
- the number of source
- the queue discipline
Queueing symbols used with Kendalls notation
Symbols
Explanation
Exponential (Markovian) inter-arrival or service time
Deterministic inter-arrival or service time
Ek
Erlang type k inter-arrival or service time
General inter-arrival or service time
1, 2, ,
Number of parallel servers or capacity
FIFO
First In, First Out queue discipline
LIFO
Last In, First Out queue discipline
SIRO
Service in random order
PRI
Priority queue discipline
GD
General queue discipline
Littles Law
Consider a queueing system for which steady state
occurs. Let = [] denote the mean long-run number in
the system, = [] denote the mean long-run waiting
time within the system, and the mean arrival rate of
jobs into the system. Also let = [ ] and = [ ]
denote the analogous quantities restricted to the queue.
Then
=
=
We also have the following results;
= + = +
= +
And
= +
= +
Examples:
M/M/1//FIFO system
G/G/c
M/G/1
M/M/1/K
M/E/3/20//SIRO
M/G/1 queue system
For the M/G/1 queueing system being operated under the FIFO service rule,
we derive the expressions of the following quantities in terms of the arrival
rate , the mean service time [], and the variance of service time 2 .
: the average time a randomly arriving customer will spend in the
system, which is composed of the waiting time in the queue and the
service time.
: the average number of people in the system that a randomly arriving
customer finds, which is composed of the number of people in the queue
and the person in service.
: the long run fraction of time the server is busy, which is equivalently the
probability that the server is busy at a random point in time.
: the long run average duration of a server busy period.
M/G/1 queueing system is a single server queueing
system in which the customer arrival process is Poisson
with rate and the service time, , for each customer
follows a general distribution with (), mean [],
and variance 2 .
Suppose we have been watching the queueing system for a
very very long time, say minutes where is very large. If
we recorded the number of minutes the server was busy
during this long period of time and then divided it by , we
would obtain , the long run fraction of time the server is
busy. During the long period of time , we would expect
there have been customers arriving to the queueing
system, each of who takes on average [] minutes to be
served. This means
number of minutes server is busy []
=
=
= []
To compute , the long run average length of a server busy
period, we again think of observing the system for a long
period of time. During this long period of time, there occur a
large number, say N, of busy periods. Since every busy period
is followed by an idle period, we could say that the number of
idle periods is N as well. (The difference between the number
of busy periods and the number of idle periods would be at
most one, and this is negligible compared to N.). Since the
average length of a busy period is B and the number of busy
periods is N, the total amount of time the server is busy, over
the long period of time we are observing, is NB.
The length of an idle period is, on average, 1/ since an idle period
occurs when the server is waiting for a customer to arrive after the
queue becomes empty. Since the arrival process is Poisson and
therefore , the server will wait a negative exponentially
distributed amount of time until the next customer arrives.
Therefore if there are N idle periods, the total amount of time the
server is idle is /. The fraction of time the server is busy, , can
now be computed by
=
=
.
1
( + ) +
Solving for and using = [], we have
/
[]
=
=
.
1 1 []
Let be a random variable denoting the amount of time
that a randomly arriving customer, say I, will spend in the
system. Our goal is to compute = []. Note that we can
decompose into the following three random variables:
1 , the remaining service time of the customer currently
in service.
2 , the time required to serve the customers waiting ahead
of me in the queue.
3 , my service time.
Clearly, = [1 ] + [2 ] + [3 ]. Since the expected
service time for each customer is [], we have
3 = []
To obtain [2 ], we first compute the conditional expectation of
T2 given that there are already customers in the system when
I, a randomly arriving customer, arrive in the system. Since one
customer is being served and 1 customers are waiting in the
queue,
1 ,
1
2 =
0,
=0
2 =
2 = =
1 ( = )
1
= []
1
Note that
we have
1 (
( = )
1
= ) = and
1 (
2 = .
= ) = . So
The expected remaining service time for the customer in service
when I randomly arrive in the system is given by
2 +
1 =
2[]
0,
1 =
1 = =
=
+
2
2
, 1
=0
2
+
2
2
( = )
Hence
= 1 + 2 + [3 ]
2
=
+
+ + E[S]
2
2
We now have one linear relationship between and . Combining this
with Littles Law, = , we have two equations for two unknowns, L
and W. A little algebra gives us
2 + 2 2
=+
.
2(1 )
Example 6
A large car dealer has a policy of providing cars for its
customers that have car problems. When a customer brings the
car in for repair, that customer has use of a dealers car. The
dealer estimates that the dealer cost for providing the service is
$10 per day for as long as the customers car is in the shop.
(Thus, if the customers car was in the shop for 1.5 days, the
dealers cost would be $15.) Arrivals to the shop of customers
with car problems form a Poisson process with a mean rate of
one every other day. There is one mechanic dedicated to those
customers cars. The time that the mechanic spends on a car can
be described by an exponential random variable with a mean of
1.6 days.
We would like to know the expected cost per day of this policy
to the car dealer. Assuming infinite capacity, we have the
assumptions of the M/M/1 queueing system satisfied, with =
0.5/ and = 0.625/, yielding a = 0.8. (Note the mean
rate is the reciprocal of the mean time.)
Using the M/M/1 equations, we have = 4 = 8 days.
Thus, whenever a customer comes in with car problems, it will
cost the dealer $80. Since a customer comes in every other day
(on the average) the total cost to the dealer for this policy is
$40 . In other words, cost is equal to $10 . But
by Littles formula, this is equivalent to $10 . The cost
structure illustrated with this example is a very common
occurrence for queueing systems. In other words if c is the cost
per item per time unit that the item spends in the system, the
expected system cost per time unit is .
References:
Feldman, R.M and Valdez-Flores,[Link] Probablity and Stochastic
[Link] Ed.,Springer Heidelbrg Dordrecht London New
York,2010.
[Link]