Page 463 - A First Course In Stochastic Models

458 APPENDICES

numbers
1 −2πik/n
c k = P (e ), k = 0, . . . , n − 1 (D.5)
n
from the explicit expression for P (z). Note that each of the points z k = e −2πik/n ,
n
k = 0, . . . , n − 1 satisfies z = 1 and thus lies on the unit circle |z| = 1. By the
power series representation of P (z) and the choice of the integer n, we have

n−1
1 −2πiℓk/n
c k ≈ p ℓ e , k = 0, . . . , n − 1.
n
ℓ=0
This relation is of the same form as (D.3). Thus the unknown probabilities p ℓ can
be calculated by applying the inverse discrete FFT method to the known vector
(c 0 , . . . , c n−1 ).

Example D.1 The M/D/1 queue

Consider the M/D/1 queue with deterministic services. In Section 2.5 it was shown
that the generating function of the limiting distribution {p k } of the number of
customers present is given by
(1 − λD)(1 − z)
P (z) = , |z| ≤ 1,
1 − ze λD(1−z)
where λ is the arrival rate of customers and D is the fixed service time of a
customer with λD < 1. Hence the state probabilities {p k } can be calculated by
applying the discrete FFT method. In the specific problem of the M/D/1 queue,
the explicit expression for the generating function P (z) is of the form Q(z)/R(z).
In such a situation one should verify whether or not R(z) has zeros on the unit
circle |z| = 1 (each zero of R(z) on the unit circle must also be a zero of Q(z)

k −2πik/n
∞
since P (z) = p k z is analytic for |z| ≤ 1). If a point z k = e is a
k=0
zero of R(z), the corresponding Fourier coefficient c k cannot be calculated directly
from (D.5) but can be found by applying L’Hospital’s rule to Q(z)/R(z) at the
point z = z k (often z 0 = 1 is a zero as is the case in the M/D/1 problem).

APPENDIX E. LAPLACE TRANSFORM THEORY

This appendix gives a brief outline of some results from Laplace transform theory
that are useful in applied probability problems. Suppose that f (x) is a continuous
real-valued function in x ≥ 0 such that |f (x)| ≤ Ae Bx , x ≥ 0, for some constants
A and B. The Laplace transform of f (x) is defined by the integral

∞
∗ −sx
f (s) = e f (x) dx
0