Page 74 - A First Course In Stochastic Models

THE POLLACZEK–KHINTCHINE FORMULA 65

Remark 2.5.1 Relation between queue size and waiting time
(∞)
Let the random variable L q be distributed according to the limiting distribution of
(∞)
the number of customers in queue at an arbitrary point in time. That is, P {L q =
(∞)
j} = p j+1 for j ≥ 1 and P {L q = 0} = p 0 + p 1 . Then the generating function
(∞)
of L q and the Laplace transform of the delay distribution are related to each
other by
(∞)
E(z L q ) = E[e −λ(1−z)D ∞ ], |z| ≤ 1. (2.5.14)
A direct probabilistic proof of this important relation can be given. Denote by
L n the number of customers left behind in queue when the nth customer enters
service. Since service is in order of arrival, L n is given by the number of customers
arriving during the delay D n of the nth customer. Since the generating function of
a Poisson distributed variable with mean δ is exp (−δ (1 − z)), it follows that for
any x ≥ 0 and n ≥ 1,
L n
E(z |D n = x) = e −λx(1−z) .
Hence
E(z ) = E[e −λ(1−z)D n ], n ≥ 1. (2.5.15)
L n
The limiting distribution of L n as n → ∞ is the same as the probability distribu-
(∞)
tion of L q . This follows from an up- and downcrossing argument: the long-run
fraction of customers leaving j other customers behind in queue when entering ser-
vice equals the long-run fraction of customers finding j other customers in queue
upon arrival. Noting that there is a single server and using the PASTA property, it
follows that the latter fraction equals p j+1 for j ≥ 1 and p 0 + p 1 for j = 0. This
(∞)
proves that the limiting distribution of L n equals the distribution of L q . Note
that, by Theorem 2.2.4, L n has a limiting distribution as n → ∞. Letting n → ∞
in (2.5.15), the result (2.5.14) follows.
Letting w q (x) denote the derivative of the waiting-time distribution function
W q (x) for x > 0, note that for the M/G/1 queue the relation (2.5.14) can be
restated as

∞ (λx)
j
p j+1 = e −λx w q (x) dx, j = 1, 2, . . . .
0 j!
The relation (2.5.14) applies to many other queueing systems with Poisson arrivals.
The importance of (2.5.14) is that this relation enables us to directly obtain the
Laplace transform of the waiting-time distribution function from the generating
(∞) 1
function of the queue size. To illustrate this, note that E(z L q ) = p 0 + [P (z)−p 0 ]
z
∞
j
for the M/G/1 queue, where P (z) = j=0 p j z is given by (2.5.8). Using this
relation together with (2.5.8) and noting that A (z) = b (λ (1 − z)), it follows from
∗
the basic relation (2.5.14) that E(e −sD ∞ ) is indeed given by (2.5.12).