Gaussian, Possion and Finite Markov Chain Imbedding Approximations for Runs and Patterns in Independent and Markov Dependent Trials

Abstract

The distribution theory of runs and patterns has been successfully used in a variety of applications including, for example, nonparametric hypothesis testing, reliability theory, quality control, DNA sequence analysis and general applied probability. The exact distributions of the number of runs and patterns are often very hard to obtain or computationally problematic, especially when the pattern is complex and n is large. Normal, Poisson and compound Possion approximations are frequently used to approximate these distributions. In this manuscript, we compare the performance of these approximations, both theoretically or numerically, to a new approximation based on the finite Markov chain imbedding technique. Both theoretically and numerically results show that, in the relative sense, the normal approximation performs the worst, the Poisson approximation performs better and the finite Markov chain imbedding approximation performs the best. Keywords: finite Markov chain imbedding, rate functions, multi-state trials