Waiting Time for an Almost Perfect Run and Applications in Statistical Process Control

A natural and intuitively appealing generalization of the runs principle arises if instead of looking at fixed-length strings with all their positions occupied by successes, we allow the appearance of a small number of failures. Therefore, the focus is on clusters of consecutive trials which contain large proportion of successes. Such a formation is traditionally called "scan" or alternatively, due to the high concentration of successes within it, almost perfect (success) run. In the present paper, we study in detail the waiting time distribution for random variables related to the first occurrence of an almost perfect run in a sequence of Bernoulli trials. Using an appropriate Markov chain embedding approach we present an efficient recursive scheme that permits the construction of the associated transition probability matrix in an algorithmically efficient way. It is worth mentioning that, the suggested methodology, is applicable not only in the case of almost perfect runs, but can tackle the general discrete scan case as well. Two interesting applications in statistical process control are also discussed.