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

n−1

i=1

Xi ,

so

μ =

n−1

i=1

E(Xi) .

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

fS,S(n, k)

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) =

∞

n=1

∞

k=1

fS,S(n,

k)xnyk

;

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