Page 70 - A First Course In Stochastic Models

THE POLLACZEK–KHINTCHINE FORMULA 61

each j that

(j) (j)
L n − Q n ≤ 1, n = 1, 2, . . . .
(j) (j)
Consequently, π j = lim n→∞ L n /n = lim n→∞ Q n /n = q j for all j. We are now
ready to prove that
(1 − z)q 0 A(z)
lim E(z Q n ) = , (2.5.7)
n→∞ A(z) − z
where
∞

A(z) = e −λt(1−z) b(t) dt
0
with b(t) denoting the probability density of the service time of a customer. Before
proving this result, we note that the unknown q 0 is determined by the fact that
the left-hand side of (2.5.7) equals 1 for z = 1. By applying L’Hospital’s rule, we
find q 0 = 1 − ρ, in agreement with Little’s formula 1 − p 0 = ρ. By the bounded
convergence theorem in Appendix A,

∞ ∞
j j
lim E(z Q n ) = lim P {Q n = j}z = q j z , |z| ≤ 1.
n→∞ n→∞
j=0 j=0
Hence, by (2.5.6) and (2.5.7),

∞
j
(1 − ρ)(1 − z)A(z)
p j z = . (2.5.8)
A(z) − z
j=0
Since the long-run average queue size L q is given by
∞ ∞

L q = (j − 1)p j = jp j − (1 − p 0 )
j=1 j=0
(see Exercise 2.28), the Pollaczek–Khintchine formula for L q follows by differen-
tiating the right-hand side of (2.5.8) and taking z = 1 in the derivative. It remains
to prove (2.5.7). To do so, note that

Q n = Q n−1 − δ(Q n−1 ) + A n , n = 1, 2, . . . ,

where δ(x) = 1 for x > 0, δ(x) = 0 for x = 0 and A n is the number of customers
arriving during the nth service time. By the law of total probability,

k
∞ (λt)
P {A n = k} = e −λt b(t) dt, k = 0, 1, . . .
0 k!