Exact Distribution of the Discrete Scan Statistic for Multi-State Higher-Order Markovian Sequences

• Activity Number: 621
• Type: Contributed
• Date/Time: Thursday, August 4, 2011 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Donald Eugene Kemp Martin*+
• Companies: North Carolina State University
• Keywords: deterministic finite automaton ; higher-order Markovian trials ; multi-state trials ; one-dimensional scan statistic ; probability generating function

Abstract

Scan statistics are used in various areas of applied probability and statistics to study local clumping of patterns. Testing based on a scan statistic requires tail probabilities. Whereas the distribution of various scan statistics has been studied extensively, most of the results are approximations, due to the difficulties associated with the computation. Results have been given to compute exact p-values for the maximum number of successes in sliding windows of length over a binary sequence that is independent or first-order Markovian. However, in many practical applications, the variables under study take on multiple values, and higher-order dependence supplies a useful model. The present paper fills this gap by obtaining the distribution of the univariate scan statistic for multi-state trials that are Markovian of a general order of dependence. A deterministic finite automaton is developed to index the computation, and matrices corresponding to automaton transitions are used to update probabilities. Numerical examples and an application to charges in a protein sequence are given to illustrate the algorithm.