Page 69 - A First Course In Stochastic Models

60 RENEWAL-REWARD PROCESSES

Substituting E(D tag ) = W q and L q = λW q , the relation becomes

2
ρE(S )
W q = λE(S)W q +
2E(S)
yielding the Pollaczek–Khintchine formula for W q .

Rigorous derivation
A rigorous derivation of the Pollaczek–Khintchine formula can be given by using
the powerful generating-function approach. Define first the random variables

L(t) = the number of customers present at time t,
Q n = the number of customers present just after the nth service
completion epoch,
L n = the number of customers present just before the nth arrival epoch.

The processes {L(t)}, {Q n } and {L n } are regenerative stochastic processes with
finite expected cycle lengths. Denote the corresponding limiting distributions by

p j = lim P {L(t) = j}, q j = lim P {Q n = j} and π j = lim P {L n = j}
t→∞ n→∞ n→∞
for j = 0, 1, . . . . The existence of the limiting distributions can be deduced from
Theorem 2.2.4 (the amount of time elapsed between two arrivals that find the sys-
tem empty has a probability density and the number of customers served during
this time has an aperiodic distribution). We omit the details. The limiting probabil-
ities can also be interpreted as long-run averages. For example, q j is the long-run
fraction of customers leaving j other customers behind upon service completion
and π j is the long-run fraction of customers finding j other customers present upon
arrival. The following important identity holds:

j = 0, 1, . . . . (2.5.6)
π j = p j = q j,
Since the arrival process is a Poisson process, the equality π j = p j is readily veri-
fied from Theorem 2.4.1. To verify the equality π j = q j , define the random variable
(j)
L n as the number of customers over the first n arrivals who see j other customers
(j)
present upon arrival and define the random variable Q n as the number of service
completion epochs over the first n service completions at which j customers are
left behind. Customers arrive singly and are served singly. Thus between any two
arrivals that find j other customers present there must be a service completion
at which j customers are left behind and, conversely, between any two service
completions at which j customers are left behind there must be an arrival that sees
j other customers present. By this up- and downcrossing argument, we have for