Handbook of Scan Statistics

Scan statistics, one of the most active research areas in applied probability and statistics, has seen a tremendous growth during the last 25 years. Google Scholar lists about 3,500 hits to references of articles on scan statistics since the year 2020, resulting in over 850 hits to articles per year. This is mainly due to extensive and diverse areas of science and technology where scan statistics have been employed, including: atmospheric and climate sciences, business, computer science, criminology, ecology, epidemiology, finance, genetics and genomics, geographic sciences, medical and health sciences, nutrition, pharmaceutical sciences, physics, quality control and reliability, social networks and veterinary science. This volume of the Handbook of Scan Statistics is a collection of forty chapters, authored by leading experts in the field, outlines the research and the breadthof applications of scan statistics to the numerous areas of science and technology listed above. These chapters present an overview of the theory, methods and computational techniques, related to research in the area of scan statistics and outline future developments. It contains extensive references to research articles, books and relevant computer software. Handbook of Scan Statistics is an excellent reference for researchers and graduate students in applied probability and statistics, as well as for scientists in research areas where scan statistics are used. This volume may also be used as a textbook for a graduate level course on scan statistics. Preface Contents About the Editors Contributors 1 Research on Probability Models for Cluster of Points Before the Year 1960 Contents Introduction The Continuous Scan Statistic Discrete Scan Statistics Summary References 2 Adaptive Likelihood Ratio Scans for the Detection of Space-Time Clusters Contents Introduction Space-Time Clusters Notation Detection of Space-Time Clusters Using LR False Alarm Rates for MAX, MIX, and W-LR Adaptive LR Detection of Space-Time Clusters Adaptive Approach in the Parametric Space Adaptive Approach for the Space of Spatial Configurations Applications Thyroid Cancer Clusters in New Mexico The Emerging Cluster Model Choosing the Estimates Results Hanseniasis Clusters in the Brazilian Amazon The Emerging Cluster Model Choosing the Estimates Results Simulated Data Study Numerical Performance of the GMAX, GMIX, and GW-ALR Scans Simulation Results Comparison with the Prospective Scan Flexibility of Shape Final Remarks References 3 Adjusted Inference for the Spatial Scan Statistic Contents Introduction Methodology Empirical Distributions (Scank) Gumbel Approximations The Gumbel Adjusted Scank Distributions Data-Driven: An Adjusted Inference Numerical Results for the Data-Driven Critical Values Variability Practical Evaluation of Critical Values Summary and Discussion Future Directions for Research References 4 Approximating the Distribution of the Multiple Scan Statistic Contents Introduction Approximations and Asymptotic Results Numerical Results Conclusions References 5 Approximations for Discrete Scan Statistics on i.i.d and Markov-Dependent Bernoulli Trials Contents Introduction Preliminaries Approximations Numerical Results Concluding Comments References 6 Bayesian Scan Statistics Contents Introduction Univariate Bayesian Scan Statistics Multivariate Bayesian Scan Statistics Fast Subset Sums Learning Models for Bayesian Spatial Scanning Alternative Approaches to Bayesian Spatial Scanning Bayesian Network Scan Statistics Bayesian Cluster Detection and Modeling Approaches Summary and Future Directions References 7 Calibrating the Scan Statistic with Size-Dependent Critical Values Contents Introduction Heuristics for Calibrating the Maximum Asymptotic Optimality Theory and Finite Sample Performance Methodology for Calibrating the Scan Statistic Related Settings The Multivariate Case Computing the Scan Statistic References 8 Demimartingale Approaches for Scan Statistics Contents Introduction Basic Definitions and Notations Results for a Simple Scan Statistic Theoretical Results Numerical Results Asymptotic Results for the Multiple Scan Statistic Theoretical Results Numerical Results Potential Applications The Demimartingale Class and Scan Statistics Summary and Future Directions References 9 Designing Distributed Sensor Detection Systems Using the Scan Statistic Contents Introduction Model Description The Suitability of the Scan Statistic Fusion Rule Designing the Detection Threshold t A Practical Upper Bound for the Probability of False Alarm A Lower Bound for the Probability of False Alarm Example 1 Ensuring that the System Satisfies a Minimum Probability of Detection Choosing Subsets C(le) When Se Is Finite Example 2 An Upper Bound for β(C,t|le-) Example 3 Designing the Cluster Set A Procedure to Design the Cluster Set C Example 4 Optimizing the Scan Statistic to Improve the Worst-Case Detection Performance Example 5 Summary and Future Directions References 10 Discrete Scan Statistics for Higher-Order Markovian Sequences Contents Introduction The Distribution of the Discrete Scan Statistic Early Exact Results Approximations and Bounds on Tail Probabilities Product-Type Approximations Poisson-Type Approximations Bonferroni-Type Bounds Product-Type Inequalities and Comparison with Bonferroni Inequalities for Dependent Sequences Exact Probabilities for Markovian Sequences 35:F 2000 35:EGW 2005 35:M 2015 Summary and Future Directions References 11 Discrete Scan Statistics Generated by Dependent Trials and Their Applications in Reliability Contents Introduction The Distribution of Sn,m Application to Reliability Summary and Future Directions References 12 Generating Function Methods for Run and Scan Statistics Contents Introduction Generalized One-Dimensional Nearest Neighbor Linear Models The Two-Step Approach Enumerations of All Blocks Special Cases of Matrix Mk Uniform wij Explicit Formulas When wij = 1 Rises and Falls Mean, Variance, and Covariance Successions Mean and Variance Summary and Future Directions References 13 Health Monitoring Techniques Using Scan Statistics Contents Introduction Scan Statistics for Linear Sequences and Grids Kulldorff's Scan Statistic and its Extensions Kulldorff's Spatial Scan Statistic and Extensions Kulldorff's Spatiotemporal Scan Statistic and Extensions Monitoring Health Processes Through Scan Statistics Using Scan Statistics for Public Health Surveillance Spatial and Spatiotemporal Scan Statistics Combination of Scan Statistics with Control Charts Bayesian Scan Statistics Scan Statistics Used at Health Organization Level Biosurveillance Systems Exploiting Scan Statistics Retrospective Analysis Through Scan Statistics Discussion References 14 Martingale Methods Contents Introduction Occurrence of a Pattern in an Independent Sequence A Gambling Approach to the Expected Value Gambling on a Generating Function Second and Higher Moments Compound Patterns and Gambling Teams Expected Time The Generating Function and Compound Patterns Second Moments and Compound Patterns Occurrence of Patterns in Markov-Dependent Trials Two-State Markov Chains and a Single Pattern Two-State Chains and Compound Patterns General Finite State Markov Chains Applications to Scans Second Moments and Distribution Approximations Summary and Concluding Observations References 15 Nearest Neighbors of Multivariate Runs Contents Introduction Notation Matrix Formula for the Generating Function of the Nearest Neighbor Linear Model The Distribution of 1 2 Nearest Neighbor Contacts GF for 1 2 Nearest Neighbor Contacts The Distribution of 1 2 Contacts: Conditional Models The Distribution of 1 2 Contacts: Unconditional Models The Distribution of 1 2 Nearest Neighbor Contacts GF for 1 2 Nearest Neighbor Contacts The Distribution of 1 2 Contacts: Conditional Models The Distribution of 1 2 Contacts: Unconditional Models Concluding Remarks References 16 New Frontiers for Scan Statistics: Network, Trajectory, and Text Data Contents Introduction Network Data Scan Statistics for Graphs Based on Spatial Data Scan Statistics for General Graphs Trajectory Data Scan Statistics for Trajectory Data Text Data Scan Statistics for Text Data Concluding Remarks and Future Directions References 17 On Scan Statistics Through the Finite Markov Chain Imbedding Approach Contents Introduction Exact Distribution of the Discrete Scan Statistic Conditional and Continuous Scan Statistics Discrete Multiple Window Scan Statistics Hypothesis Testing Summary References 18 On the Exact Distributions of Pattern Statistics for a Sequence of Binary Trials: A Combinatorial Approach Contents Introduction and Preliminaries General Results for Model Sequences Exchangeable Trials Markov-Dependent Trials Exact Distributions: Statement of the Problem Counting Statistic Waiting Time Statistic Patterns of Limited Length and Related Statistics Definitions and Notation Exact Distributions via Combinatorial Analysis Combinatorial Results Exact Distributions Conclusions References 19 Poisson Approximations for the Number of kl-Scans Contents Introduction Comparisons with Two-Dimensional Discrete Scan Statistics Poisson Approximation Future Directions References 20 Run and Scan Rules in Statistical Process Monitoring Contents Introduction Process Monitoring and Control Charts The Shewhart Control Chart Insensitivity of Shewhart Control Charts and Remedial Techniques Phase I and Phase II Analysis Run-Length Distribution Zero-State and Steady-State Mode Run and Scan Rules The CW Runs Rules The DR Runs Rules The KL Runs Rules The KA Runs Rules The AR Runs Rules Other Scan-Based Stopping Rules Review of Run and Scan Rules for Process Monitoring Control Charts for Process Average Control Charts for Process Variance Control Charts for Attributes Time-Between-Events Control Charts with Runs Rules Nonparametric Control Charts with Runs Rules Switching Rules Based on Run and Scan Statistics Multivariate Control Charts with Runs Rules Time-Weighted Charts with Runs Rules Concluding Remarks and Future Research References 21 Scan Statistics Applications in Genomics Contents Introduction Underlying Probabilistic Models Events in Poisson Processes Points Uniformly Distributed on the Unit Interval or Unit Square Sequence of Bernoulli Random Variables Various Extensions DNA Sequence Analyses Chromosomal Translocation Viral DNA Integration Copy Number Variation Clusters of Single Nucleotide Variants in CNV Regions Extracting Disease-Associated Gene Clusters from a Whole Gene Pathway Future Developments References 22 Scan Statistics for Detecting a Local Change in Mean for Normal Data Contents Introduction Approximations and Inequalities for a Fixed-Window Scan Statistic Sequential Monitoring with a Moving Window of Fixed Length Multiple- and Variable-Window Scan Statistics Numerical Results Summary References 23 Scan Statistics for Detecting a Local Change in Model Parameters for Normal Data Contents Introduction Scan Statistics for One-Dimensional Normal Data Fixed Window Scan Statistics Multiple and Variable Window Scan Statistics Scan Statistics for Two-Dimensional Normal Data Fixed Window Scan Statistics Multiple and Variable Window Scan Statistics Numerical Results Summary References 24 Scan Statistics for Integer-Valued Random Variables: Conditional Case Contents Introduction Bernoulli Model Exact Results Product-Type Approximations Bonferroni-Type Inequalities Poisson Approximations Compound Poisson Approximations Approximations and Inequalities for the Expected Size and Standard Deviation of the Scan Statistic An Experiment in Molecular Biology Binomial Model Poisson Model Negative Binomial Model Approximations for the Distribution of a Multiple Occurrence Scan Statistic Numerical Results Concluding Remarks References 25 Scan Statistics on Graphs and Networks Contents Introduction Simple Graphs Time Series in Graphs A Purely Spatial Framework The Spatiotemporal Model Time Series of Hypergraphs Graph Model Scan Statistics Application to the Enron Data Time Series of Attributed Graphs Graph Model Scan Statistics Application to the Enron Data Heterogeneous Graphs Social Media Experiment Random Geometric Graphs Scan Statistics on Erdös-Rényi Graphs Focusing Results Algorithms for Approximating the Distribution of Scan Statistics Lovász Extended Scan Statistic Graph Fourier Scan Statistic (GFSS) Concluding Remarks References 26 Scan Statistics Viewed as Maximum of 1-Dependent Random Variables Contents Introduction Application to One-Dimensional Scan Statistics One-Dimensional Discrete Scan Statistic Scan Statistics for i.i.d. Yi's Scan Statistics for d-dependent Yn's One-Dimensional Continuous Scan Statistics Application to Multidimensional Scan Statistics Two-Dimensional Discrete Scan Statistic Three-Dimensional Discrete Scan Statistics Two-Dimensional Continuous Scan Statistics Summary References 27 ScanZID: Spatial Scan Statistics with Zero Inflationand Dispersion Contents Introduction Background Zero-Inflated Dispersion Model: ZID Examples of the ZID Model NB-ZID(μi,φ,p) Model The DP-ZID(μi,φ,p) Model GP-ZID(μi,φ,p) Model Spatial Scan Statistics Spatial Scan Statistics with Inflated Zeros and Overdispersion: ScanZID ScanZID Models Fast Double Bootstrap-EM for the p-Value Computation Application: Hanseniasis Clusters in the Amazonas State – Brazil Final Remarks References 28 Shocks, Scans, and Reliability Systems Contents Introduction The δ-Shock Model and Scans Concluding Remarks References 29 Spacing Methods and Their Applications to Scan Statistics Contents Introduction Applications The Distribution of the Scan Statistic The Distribution of the Multiple Scan Statistic General Algorithm Basic Recursion Reduction Recursion The Marking and Two-Stage Algorithms References 30 Spatial Cluster Detection Through a Dynamic Programming Approach Contents Introduction Dynamic Spatial Cluster Detection Scan Geometric Constraints Inference Numerical Studies A Real Data Set Concluding Remarks Appendix Multi-objective Optimization Problem References 31 Spatial Cluster Estimation and Visualization Using Item Response Theory Contents Introduction Basic Concepts of IRT Spatial Cluster Estimation Using IRT Preparing the Data Needed for the IRT Analysis IRT Analysis Goodness-of-Fit Test Numerical Simulations Studies Comparison with the Intensity Function Real Data Application Conclusions References 32 Spatial Scan Statistics for Functional Data Contents Introduction Spatial Clusters of Functional Data Spatial Scan Statistics for Functional Data Spatial Scan Statistics for Univariate Functional Data Spatial Scan Statistics for Multivariate Functional Data Choosing the Appropriate Method Application Discussion and Perspectives References 33 The Role of Scan Statistics in High-Energy Astrophysics Contents Introduction The iSRS Method Application of the iSRS Clustering Scheme Directions for Future Research Conclusions References 34 The Scan Statistic for Multidimensional Data and Social Media Applications Contents Introduction Review of Applications Review of Efficiency and Effectiveness of the Scan Statistic Size and Shape of the Scanning Windows Multiple Clusters or Multiple Size Windows (Robustness) Distribution of the Scan Statistic and Approximations Moving Beyond the Spatiotemporal Scan Statistic into Multidimensions The Scan Statistic and Social Media Sadness Fear Anger Joy Love Summary of Results from Other Parts of the World References 35 The Spatial Structure of Housing Prices in Madrid: Evidence from Spatio-temporal Scan Statistics Contents Introduction Economic Applications of Scan Statistics Spatio-Temporal Scan Statistics The Scan Statistic for Normal Data in Cross Section The Spatio-Temporal Version of the Scan Test Prospective and Retrospective Analysis Application on Housing Submarkets in the City of Madrid Data and Descriptive Statistics Results All Submarkets Attics Houses Small Flats Standard Flats Large Flats Conclusion References 36 Two-Dimensional Discrete Scan Statistics with Arbitrary Window Shape Contents Introduction Two-Dimensional Discrete Scan Statistics with Arbitrary Window Shape Arbitrary Discrete Scanning Window Shape Approximation for the Distribution of SG̃ Numerical Applications: Approximation and Power of the Scan Statistic Test Approximation and Scanning Window Shape Power of the Scan Statistic Test: Window and Cluster Shapes Discussion References 37 Variable Window Scan Statistics forPoisson Processes Contents Introduction Scan Statistics Four Problems with Scan Statistics The Window Size Problem The Background Rate Problem The Low-End Problem The Online Problem Experiments and Results Synthetic Data Snowfall Data Earthquake Data Conclusion References 38 Variable Window Scan Statistics: Alternatives to Generalized Likelihood Ratio Tests Contents Introduction Scan Statistics for Point Processes Likelihood-Based Scan Statistics Alternative Scan Statistics Scan Statistics for Marked Point Processes Likelihood-Based Scan Statistics Two Nonparametric Scan Statistics A Distribution-Free Scan Statistic A Mann-Whitney Scan Statistic Comparing Parametric and Nonparametric Scan Statistics Unmarked Point Processes Marked Point Processes An Application to Epidemiological Data Unmarked Approach Marked Approach Summary and Future Directions References 39 Waiting for Scans Containing Two Successes Contents Introduction Waiting Time for the First Scan of Type 2/r Distribution of T2,r Bounds and Approximations Waiting Time for Multiple Scans of Type 2/r Distribution of T(m,I)2,r Distribution of T2,r(m,II) Applications Quality Control Queuing Models Radar Detection Weaning from Mechanical Ventilation Conclusions References 40 Wilcoxon Rank Sum Scan Statistics for Continuous Data with Outliers Contents Introduction Fixed Window Scan Statistics One-Dimensional Data Two-Dimensional Data Multiple Window Scan Statistics One-Dimensional Data Two-Dimensional Data Numerical Results Concluding Remarks References