Page 456 - A First Course In Stochastic Models

C. GENERATING FUNCTIONS 451

with parameter α i = 1 − (i − 1)/r. The generating function of Y i is
∞
k−1 k α i z
P i (z) = α i (1 − α i ) z = .
1 − (1 − α i )z
k=1
Noting that α 1 = 1 and letting β i = 1 − α i = (i − 1)/r, it follows from (C.3) that

k
∞
the generating function P (z) = P {X = k}z is given by
k=1
α 2 · · · α r z r
P (z) = P 1 (z) · · · P r (z) = .
(1 − β 2 z) · · · (1 − β r z)
Using partial-fraction expansion, we next find
γ 2 γ r
P (z) = α 2 · · · α r z r + · · · + ,
1 − β 2 z 1 − β r z
where the residue γ i is given by

1
r
"
γ i = , i = 2, . . . , r.
1 − β ℓ /β i
ℓ=2
ℓ =i

∞ j−1 j
Noting that j=1 (1−p)p z = (1−p)z/(1−(1−p)z), we can invert the final
expression for P (z) to obtain

P {X = k} = α 2 · · · α r γ 2 β k−r + · · · + γ r β k−r , k ≥ r. (C.4)
2 r
Example C.2 Success runs
Another illustration of the usefulness of the generating function approach is the
analysis of success runs in independent Bernoulli trials. How do we compute the
probability that in n independent Bernoulli trials with success probability p there is
some sequence of s consecutive successes? For fixed s, denote this probability by

n
P n for n ≥ 0. The probability P n can be written as P n = p j for n = 0, 1, . . . ,
j=0
where the probability p j is defined as
p j = the probability that for the first time a sequence of s
consecutive successes occurs at the jth trial.
∞
Note that {p j , j = 0, 1, . . . } is a probability distribution with
j=0 p j = 1.
s
Obviously p j = 0 for j < s and p s = p . For j > s, we have the recursion
s
k−1
p j = p (1 − p)p j−k , j = s + 1, s + 2, . . . .
k=1
To prove this, fix j > s and denote by A the event that a sequence of s consecu-
tive successes occurs for the first time at the jth trial. The event A can only occur