Page 72 - A First Course In Stochastic Models

THE POLLACZEK–KHINTCHINE FORMULA 63

Let λ w and λ m denote the average arrival rates of women and men. Let µ w and
c w denote the mean and the coefficient of variation of the amount of time a woman
spends in the loo. Similarly, µ m and c m are defined for men. It is assumed that
λ w µ w < 1. Using the assumptions λ w = λ m , µ w = 2µ m and c w ≥ c m , it follows
from (2.5.2) and the Pollaczek–Khintchine formula (2.5.3) that
the average queue size for the women’s loo
1 2 (λ w µ w ) 2 1 2 (2λ m µ m ) 2
= (1 + c ) ≥ (1 + c )
w
m
2 1 − λ w µ w 2 1 − 2λ m µ m
1 2 (λ m µ m ) 2
≥ 4 × (1 + c ) .
m
2 1 − λ m µ m
Hence
the average queue size for the women’s loo
≥ 4 × (the average queue size for the men’s loo).
The above derivation uses the estimate 1 − 2λ m µ m ≤ 1 − λ m µ m and thus shows
that the relative difference actually increases much faster than a factor 4 when the
utilization factor λ w µ w becomes closer to 1.

Laplace transform of the waiting-time probabilities ∗
The generating-function method enabled us to prove the Pollaczek–Khintchine
formula for the average queue size. Using Little’s formula we next found the
Pollaczek–Khintchine formula for the average delay in queue of a customer. The
latter formula can also be directly obtained from the Laplace transform of the
waiting-time distribution. This Laplace transform is also of great importance in
itself. The waiting-time probabilities can be calculated by numerical inversion of
the Laplace transform; see Appendix F. A simple derivation can be given for the
Laplace transform of the waiting-time distribution in the M/G/1 queue when
service is in order of arrival. The derivation parallels the derivation of the generating
function of the number of customers in the system.
Denote by D n the delay in queue of the nth arriving customer and let the random
variables S n and τ n denote the service time of the nth customer and the time elapsed
between the arrivals of the nth customer and the (n+1)th customer. Since D n+1 = 0
if D n + S n < τ n and D n+1 = D n + S n − τ n otherwise, we have

+
D n+1 = (D n + S n − τ n ) , n = 1, 2, . . . , (2.5.10)
where x + is the usual notation for x = max(x, 0). From the recurrence formula
(2.5.10), we can derive that for all s with Re(s) ≥ 0 and n = 1, 2, . . .

(λ − s)E e −sD n+1 = λE e −sD n b (s) − sP {D n+1 = 0}, (2.5.11)
∗
∗ This section can be skipped at first reading.