Page 455 - A First Course In Stochastic Models

450 APPENDICES

are readily obtained from P (z). For example, the first two moments are obtained
from the relations

∞ ∞

′
′′
kp k = P (1) and k(k − 1)p k = P (1).
k=0 k=1
In general the relation (C.1) is only of theoretical value. It is often possible to
obtain an explicit expression for P (z) when the probabilities p k are unknown (e.g.
from a difference equation for the p k ). In Appendix D we discuss the discrete
Fast Fourier Transform algorithm to recover the p k numerically when an explicit
expression for P (z) is available. Usually it is not possible to analytically recover
the p k from (C.1).
A useful probabilistic interpretation can be given to P (z). If the random variable
N is distributed according to {p k }, then

N
P (z) = E(z ). (C.2)
A direct consequence of this relation is that the generating function of the con-
volution of two discrete probability distributions is the product of the generating
functions of these two probability distributions. More specifically, suppose that the
random variable N = X + Y, where X and Y are two independent discrete ran-
dom variables with respective probability distributions {a k , k = 0, 1, . . . } and {b k ,
k = 0, 1, . . . } . Let p k = P {N = k}, k = 0, 1, . . . . Then the generating function
P (z) of the distribution {p k } is given by

P (z) = A(z)B(z), (C.3)

where A(z) and B(z) are the generating functions of the probability distributions
Y
X
{a k } and {b k }. This follows from E(z X+Y ) = E(z )E(z ). In practice it is usually
faster to compute the p j by applying the discrete Fast Fourier Transform method
j

a
rather than using the convolution formula p j = k=0 j−k b k for j ≥ 0.
Example C.1 The coupon-collecting problem
Suppose there are r different types of coupons and each time we obtain a coupon it
is equally likely to be any one of the r types. How do we compute the probability
distribution of the number of coupons we need to collect for a complete set of
coupons? Denote this number by the random variable X. The random variable X
can be written as
X = Y 1 + · · · + Y r ,

where Y i is the number of additional coupons that need to be collected to increase
the number of different coupons in the collection from i −1 to i. The random vari-
ables Y 1 , . . . , Y r are independent of each other and Y i has a geometric distribution