Page 353 - A First Course In Stochastic Models

348 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

The recursion (9.2.1) enables us to compute recursively p 1 , p 2 , . . . starting with
p 0 = 1 − ρ. In Section 2.5 we proved that p 0 = 1 − ρ; see also relation (9.1.3).
The recursion scheme is numerically stable, since the calculations involve only
additions with positive numbers and thus cannot cause a loss of significant digits.
For many service-time distributions of practical interest, numerical integration can
be avoided for the computation of the constants a n . Explicit expressions for the a n
can be given for the cases of deterministic and phase-type services.
Define the generating function P (z) by

∞
j
P (z) = p j z , |z| ≤ 1.
j=0

j
Multiplying both sides of (9.2.1) by z and summing over j, it is a matter of simple
algebra to derive that

∞ ∞
n n
P (z) − p 0 = λp 0 z a n z + λ{P (z) − p 0 } a n z .
n=0 n=0
Since p 0 = 1 − ρ, we obtain

1 − λ(1 − z)α(z)
P (z) = (1 − ρ) , (9.2.8)
1 − λα(z)

∞ n
a
where α(z) = n=0 n z is given by
∞

−λ(1−z)t
α(z) = {1 − B(t)}e dt.
0

∞ −λ(1−z)t
Expression (9.2.8) for P (z) coincides with expression (2.5.8), since e
0
b(t) dt = 1−λ(1−z)α(z) when b(t) is the probability density of the service time.
The discrete FFT method provides an alternative method for the computation of the
state probabilities using the explicit expression (9.2.8) for the generating function
P (z). A by-product of (9.2.8) is the famous Pollaczek–Khintchine formula
2
2
λ E(S )
L q = (9.2.9)
2(1 − ρ)
for the long-run average queue size. Using Little’s formula L q = λW q , it follows
that the long-run average delay in queue per customer is given by
2
λE(S )
W q = . (9.2.10)
2(1 − ρ)