84 1. Streaks
calculation below does not generalize. Let Xi, for 1 ≤ i ≤ n − 1,
denote the random variable that is 1 if the i’th and (i+1)’st outcomes
disagree. Then the average number of runs is just
But for each i, the probability that Xi = 1 is just 2pq, so for each i,
E(Xi) = 2pq ,
so the average number of runs is just
= 1 + 2p(1 − p)(n − 1) .
In the Markov chain model, the situation is more complicated(!).
We will not go into the details here, but rather give an outline of how
to proceed. We write
for the probability that a sequence of n trials begins and ends with
a success and has k runs. The quantities fS,F , fF,S and fF,F are
defined similarly. We define the generating function
GS,S(x, y) =
the functions GS,F , GF,S, and GF,F are defined in a similar manner.
One can show that
GS,S(x, y) = p2xyGS,F (x, y) + p1xGS,S(x, y) + xy ,
GS,F (x, y) = (1 − p1)xtGS,S(x, y) + (1 − p2)xGS,F (x, y) ,
GF,S(x, y) = p2xyGF,F (x, y) + p1xGS,F (x, y) ,
GF,F (x, y) = (1 − p1)xyGS,F (x, y) + (1 − p2)xGF,F (x, y) + xy .
Note that two of these equations are homogeneous (there are no
summands on the right-hand sides that do not involve the functions
G∗,∗). Thus, for example, using the second equation above, it is easy