Page 475 - A First Course In Stochastic Models

470 APPENDICES

for the waiting-time distribution function W q (t) in the M/G/1 queue with service
in order of arrival. Then it follows from the representation (8.2.10) that W q (t)
for 0 ≤ t ≤ t 0 requires the service-time density b(t) only for 0 ≤ t ≤ t 0 . If the
Laplace transform b (s) of the density b(t) is analytically intractable, the idea is
∗
to approximate the density b(t) by a polynomial P (t) on the interval [0, t 0 ] and by
zero outside this interval. Consequently, the intractable Laplace transform b (s) is
∗
approximated by a tractable expression
t 0

b ∗ (s) = e −st P (t) dt.
app
0
A naive approach uses a single polynomial approximation P (t) for the whole inter-
val [0, t 0 ]. A polynomial approximation that is easy to handle is the Chebyshev
approximating polynomial. Gauss–Legendre integration is then recommended to
evaluate the required function values of b ∗ (s). A code to compute the func-
app
tion values of the Chebyshev approximating polynomial at the points used in the
numerical integration procedure can be found in the sourcebook by Press et al.
(1992). One has a smooth function P (t) when using a single Chebyshev polyno-
mial approximation P (t) for the whole interval [0, t 0 ]. However, a better accuracy
is obtained by a more refined approach in which the function b(t) on the interval
[0, t 0 ] is replaced by a piecewise polynomial approximation on each of the subin-
tervals of length with as in (F.2). Den Iseger (2002) suggests approximating
b(t) on each of the subintervals [k , (k + 1) ) by a linear combination of Leg-
endre polynomials of degrees 0, 1, . . . , 2n − 1 with n as in (F.2). This leads to an
approximating function with discontinuities at the points k . However, this diffi-
culty can be resolved by the modification (F.7) for non-smooth functions. Details
can be found in Den Iseger (2002). A simpler approach seems possible when the
analytically intractable Laplace transform b (s) is given by b (s) = E(e −sX ) for
∗
∗
a continuous random variable X with a strictly increasing probability distribution
function F(x). Then b (s) = E[g(U, s)] for a uniform (0, 1) random variable
∗
U, where g(u, s) = exp(−sF −1 (u)). The (complex) integral 1 g(u, s) du can be
0
evaluated by Gauss–Legendre integration. The required numerical values of the
inverse function F −1 (u) may be obtained by using bisection.
APPENDIX G. THE ROOT-FINDING PROBLEM

The analysis of many queueing problems can be simplified by computing first the
roots of a certain function inside or on the unit circle in the complex plane. It is a
myth that the method of finding roots in the complex plane is difficult to use for
practical purposes. In this appendix we address the problem of finding the roots of
the equation
c λD{1−β(z)}
1 − z e = 0 (G.1)

∞ j
β
inside or on the unit circle. Here c is a positive integer, β(z) = j=1 j z is the
generating function of a discrete probability distribution {β j , j ≥ 1} and the real