THE POISSON PROCESS

G A Vignaux

Abstract

This is Revision: 2.1 .

Contents

References

[(Hillier and Lieberman)(1990)]

Hillier, F. S. and Lieberman, G. J. (1990). Introduction to Operations Research. McGraw-Hill, 5th edition.

[(Taha)(1992)]

Taha, H. A. (1992). Operations Research: An Introduction. Macmillan, 5th edition.

[(Winston)(1994)]

Winston, W. L. (1994). Operations Research, Applications and Algorithms. Duxbury Press, 3rd edition.

1  Introduction

The Poisson Process is the model we use in Queuing theory for ``Random arrivals''. It is in many ways the simplest model we could use for arrivals into a queue system because it assumes that the probability of an arrival in a small interval of time depends only on the size of the interval, not on any history of the process to that time.

The main reference for these notes is [(Hillier and Lieberman)(1990)]. Other OR books, such as [(Taha)(1992)] and [(Winston)(1994)] also explain the model. Many other books on statistics and queue models deal with this important stochastic process.

2  The Poisson Process

Small time interval h. Prob(event in interval h) = lh

• The probability of an event in h depends only on the length of h and not on its position, t.

• Hence the system has no memory - it does not matter how long since an event last occurred. Constant probability of an arrival. The process has no memory This is the Markovian property.

• We choose to make h and l small enough so that at most one event will occur in h.

• l is called the event rate or arrival rate

2.1  Merging (or adding) two Poisson streams

Prob{event in stream 1 is in h } = l₁ h
Prob{event in stream 2 is in h } = l₂ h

Prob{some event is in h}

= Prob{stream 1 event} + Prob{stream 2 event} = l1 h + l2 h = (l1 + l2)h

Merged stream acts like a Poisson process with rate

l = l1 + l2

2.2  Partitioning two streams

Whenever an event (arrival) occurs we decide to divert it into A or B stream according to fixed probabilities, p_A and p_B.

Prob{A event in h}

= prob{event in h} × Prob{choosing A stream} = lpA h

The A stream acts like a Poisson stream with a rate of events = p_Al

2.3  The probability that NO events occur in an interval T

P{0 events in interval [t, t+h] } = 1 - lh where lh << 1

put

p0(t) = P{0  events in [0, t] } p0(t+h) = P{ 0  events in [0, t+h]}

Since probability of an event in h is independent of any others:

p0(t+h) = p0(t).(1 - lh) p0(t+h) - p0(t) = - lh p0(t) p0(t+h) - p0(t) h = - lp0(t)

and as h ® 0

dp0(t) dt = - lp0(t) dp0(t) p0(t) = - ldt

integrate

lnp0(t) = const - lt, p0(t) = Ae-lt

But note that if t ® 0, p₀(t) ® 1 ( certain to have 0 events!)

p0(t) = e-lt

2.4   The probability of n events in an interval T.

pn(T) = Prob { n  events in   [0, T] } p0(T) = Pr { 0 events in [0, T] } = e- lT p1(T) = Pr{ 0 ev. in [0, T]} ×Pr{1 ev. in [t, t+h]} ×Pr{0 ev. in [t+h, T] }         (int over all t from 0 to T), h ® 0 = ó õ T 0  e- lt l dt e- l(T - t) = le- lT ó õ T 0   dt p1(T) = lT e- lT

The probability of 2 events in [0, t] is

p2(T) = ó õ Prob{1 event in [0, t] } ×(l dt) ×Prob{0 events in [t, T-t] }         (int over all t from 0 to T), h ® 0 = ó õ T 0  (lt e- lt)(l dt) e- l(T-t) = l2 e- lT ó õ T 0  t dt p2(T) = (lT)2 2 e- lT

This leads us to the Poisson distribution

pn(T) = (lT)n n! e- lT

E(n) = lT     Var(n) = lT

2.5  How long to go before the next event?

Prob{next event after 0 occurs in [t, t+h] }

= Prob{0 events in [0, t] } ×Prob {1 event in [t, t+h] } = e - lt.lh

thus p.d.f.

f(t) = le- lt

NOTE

• exponential distribution

• E(t) = 1/l

• std. deviation = 1/l

• variance = 1/l²

2.6  How long between events?

Since no memory the zero point can be an event.

Thus time between events is also exponential, l.

f(t) = le- lt

the average time between events = 1/l.

2.7  The distribution of time to the k-th next event

Prob{kth next event is in [t, t+h] }

= Prob{k-1 events in [0, t] } (lh) = (lt)k - 1 (k-1)! e- lt lh

Thus p.d.f. is

fk(t) = l(lt)k-1 (k-1)! e-lt

This is an Erlang distribution with mean = k /l and variance = k/l². It has shape parameter of k.

3  The Erlang Distribution, E_k

The Erlang Distribution is important in queueing theory and simulation.

Named after A K Erlang, a Danish telephone engineer, considered to be the founder of queueing theory. He wrote papers in 1917-1918.

The E_k is a continuous rv with density function

f(t) = (mk)k (k-1)! tk-1e-kmt

A special type of Gamma distribution with an integer shape parameter. 2 parameters control its distribution (the scale parameter, m and its shape parameter, k). Mean is 1/m and its variance 1/km².

• A form of Gamma distribution with an integer parameter.
• when k = 1 we have the exponential
  

  f(t) = (m)1 1! t0e-mt = memt

• mean 1/m
• variance 1/km²
• Std. deviation = 1/Ökm

The Erlang distribution gets narrower as k increases. As k tends to infinity the variance tends to zero. Thus the Erlang can also represent the ``distribution'' of a constant - a deterministic value.

An intermediate value of k gives a shape between exponential and constant.

3.1  The Erlang distribution as sum of exponentials

The Erlang can be thought of as the convolution (that is the sum of) k independent exponential random variables (each with the same mean).

To get a mean of 1/m these k exponentials must each have mean 1/km.

The variance of each exponential is 1/k²m². Thus variance of their sum is k/k²m² = 1/km².

It is an important distribution in queueing theory because

1. we can simulate an Erlang rv , E_k, by summing k exponential rvs,
2. we can consider it as if it was a sequence of phases each of exponential type. Thus we can use the Markovian property and get some theoretical results with the Erlang. This is what Erlang did.