A recursive algorithm for computing the distribution of the number of successes in higher-order Markovian trials

This paper presents a recursive method of computing the distribution of the number of successes in a sequence of binary trials that are Markovian of a general order. Waiting-time distributions are also obtained. Recurrence relations among probabilities of partitioned events are used to compute the desired probabilities. An advantage of computing the probabilities in the manner given is that the algorithm may be easily programmed on a computer, requiring no computer algebra system, as in computation based on conditional probability generating functions. The difference between calculated probabilities for various model orders emphasizes the importance of selecting a proper model order for a Markovian data set.