An Algorithm for Calculating the Distribution of Runs and Patterns - The Finite Markov Chain Imbedding Approach

Fu and Koutras presented a novel approach to calculate the probability of the number of the appearance of a pattern in a sequence. However, how to formulate the transition matrix is a trick step in this approach. It might depend on the pattern you want to count and the structure of the sequence. We would like to present an algorithm for constructing such a transition matrix for a layman, i.e.any person who knows how to write a program shall be able to calculate the probability. We will present several examples for demonstration. This new algorithm enables usto find the conditional probability given that the pattern has appeared unknown n times at the beginning of an observed sequence.