Page 351 - A First Course In Stochastic Models

346 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

the state probabilities, the discrete FFT method provides an alternative method to
compute the state probabilities. In Section 9.2.2 we discuss the computation of the
waiting-time probabilities when service is in order of arrival. Also attention is paid
to an approximation for the waiting-time distribution. This approximation is based
on the asymptotic expansion of the tail of the waiting-time distribution. Further, we
discuss a simple but generally useful two-moment approximation for the waiting-
time percentiles. Section 9.2.3 discusses the probability distribution of the length
of a busy period and the computation of the waiting-time probabilities when the
last-come first-served discipline is used. The distribution of work in system is the
subject of Section 9.2.4.

9.2.1 The State Probabilities
The time-average probability p j can be interpreted as the long-run fraction of
time that j customers are in the system. Using a basic result from the theory of
regenerative processes and a simple up- and downcrossing argument, we derive a
numerically stable recursion scheme for the state probabilities p j .
Theorem 9.2.1 The state probabilities p j satisfy the recursion

j

p j = λa j−1 p 0 + λ a j−k p k , j = 1, 2, . . . , (9.2.1)
k=1
where the constants a n are given by
∞ (λt)
n
−λt
a n = e {1 − B(t)} dt, n = 0, 1, . . . .
0 n!
Proof The stochastic process {L(t), t ≥ 0} describing the number of customers
in the system is regenerative. The process regenerates itself each time an arriving
customer finds the system empty. Denoting by a cycle the time elapsed between two
consecutive arrivals who find the system empty, we define the random variables

T = the length of one cycle,
T j = the amount of time that j customers are present during one cycle

for j = 0, 1, . . . . The expected length of one cycle is finite (this is in fact a
by-product of the analysis in Section 2.6). By Theorem 2.2.3,
E(T j )
p j = , j = 0, 1, . . . . (9.2.2)
E(T )
By the lack of memory of the Poisson process, E(T 0 ) = 1/λ and so

1
p 0 = . (9.2.3)
λE(T )