Page 457 - A First Course In Stochastic Models

452 APPENDICES

if one of the mutually exclusive events B 1 , . . . , B s occurs, where B k is the event
that each of the first k − 1 trials have success as outcome but the kth trial does
not. Noting that P (A) = p j , P (B k ) = p k−1 (1 − p) and P (A | B k ) = p j−k , the
recursion follows by applying the law of conditional probabilities. As an alternative
to the recursion scheme, the probabilities p j can also be numerically obtained by
numerical inversion of the generating function. Multiplying both sides of the above
j
recursion for p j by z and summing over j, it follows that the generating function

j
∞
P (z) = p j z satisfies
j=0
∞ s
s j k−1
P (z) = p s z + z p (1 − p)p j−k
j=s+1 k=1
s ∞
s k k−1 j−k
= p s z + z p (1 − p) p j−k z
k=1 j=s+1
s
k k−1
s
= p s z + P (z) z p (1 − p).
k=1
This gives
s s
p z
P (z) = . (C.5)
s
k−1 k
1 − p (1 − p)z
k=1
Hence an explicit expression has been obtained for the generating function P (z) of
the unknown probabilities {p j }. Using this expression the unknown probabilities p j
can also be numerically obtained by applying the discrete Fast Fourier Transform
method from Appendix D. A simple but extremely useful method to compute p j for
large j is to use an asymptotic expansion. This approach will be discussed below in
a general setting. To do so, some basic concepts from complex function theory are
needed such as the concept of an analytic function. In a nutshell, a function on a
domain in the complex plane is called analytic when the function is differentiable
infinitely often on that domain. A fundamental theorem from complex function
theory states that a function f (z) is analytic in the complex region |z| < R if
∞

n
and only if f (z) allows for the power series representation f (z) = f n z for
n=0
|z| < R.
Asymptotic expansion

j
∞
Suppose that the generating function P (z) = p j z of an (unknown) proba-
j=0
bility distribution {p j , j = 0, 1, . . . } has the form
N(z)
P (z) = . (C.6)
D(z)
The generating function P (z) is defined for |z| ≤ 1, but assume that N(z) and
D(z) are analytic functions whose domains of definition can be extended to a