7. Appendix 87

If one lets p1 = p2, so that the Bernoulli model is obtained, one can

check that the result agrees with the one already obtained.

The two graphs show what one might expect, namely that the

expected number of runs in the Markov model is less than in the

Bernoulli trials model. It is easy to show this; one need only show

that if p1 p2, then

Ω1 2p(1 − p) .

Next, it might be nice to show that the runs distribution corre-

sponding to GS,S(x, y) is asymptotically normal. One might need to

do this to discuss the power of the test that compares the two models.

We also might try writing approximation algorithms for the cal-

culation of these probabilities, since the probabilities fall off rapidly

and it is time-consuming to calculate the sums using the exact ex-

pressions.

The distribution of the length of the longest success run in the

Markov chain model can be calculated using recursions. We define

A(n, x, k, p1,p2) to be the probability that a Markov sequence, begin-

ning with a success, has no success run exceeding x in length, and

ends with k successes, for 0 ≤ k ≤ x. This function satisfies the fol-

lowing equations. First, if n = 1, then the function is 1 if k = 1 and

0 otherwise. If n 1, then if k 1,

A(n, x, k, p1,p2) = A(n − 1,x,k − 1,p1,p2)p1 ,

since a sequence of length n that ends in k successes is obtained from

one of length n − 1 that ends in k − 1 successes by adding one success

to the end, and this happens with probability p1, since k 1. If

n 1 and k = 1, then

A(n, x, 1,p1,p2) = A(n − 1,x, 0,p1,p2)p2 ,

since in this case we are adding a success to the end of a sequence

whose last state was the failure state. Finally, if n 1 and k = 0,