Discrete Scan Statistics for Higher-Order Markovian Sequences

In this chapter we review methods for computing probabilities of the discrete scan statistic. Most of the presented results are for independent trials, as results for higher-order Markovian sequences are scarce. Results from three papers on exact computation of probabilities in Markovian sequences are given, two of which are for binary Markov chains, the third allowing multistate higher-order Markovian trials. Whereas exact computation of the complete distribution of the statistic is limited to relatively small values of the scanning window w, larger window sizes can be handled in the case of individual p-values and extreme values of the scan statistic. Approximations and bounds on probabilities for the statistic have been developed for still larger values of w. Product-type and Poisson/compound Poisson approximations are considered here, as well as Bonferroni- and product-type bounds that give a feel for the accuracy of approximations. The final section includes numerical comparisons of exact and approximate methods to evaluate the accuracy of the approximations and possible areas of future study.