Abstract: We introduce a new method analyzing the cumulative sum (CUSUM) procedure in sequential change-point detection. When observations are phase-type distributed and the post-change distribution is given by exponential tilting of its pre-change distribution, the first passage analysis of the CUSUM statistic is reduced to that of a certain Markov additive process. By using the theory of the so-called scale matrix and further developing it, we derive exact expressions of the average run length, average detection delay, and false alarm probability under the CUSUM procedure. The proposed method is robust and applicable in a general setting with non-i.i.d. observations. Numerical results also are given.
Introduction
Sequential change-point detection is a critical task in statistical monitoring, aimed at identifying shifts in a system's underlying distribution as rapidly as possible while controlling for false alarms. The Cumulative Sum (CUSUM) procedure is a cornerstone of this field, widely applied in quality control, finance, and engineering. Despite its popularity, exact performance analysis for discrete-time CUSUM has historically been elusive. Researchers have traditionally relied on approximations, such as Wald’s approximation or renewal theory, which often lack the precision required for complex, non-i.i.d. data streams. This paper addresses these limitations by reframing the CUSUM problem through the lens of continuous-time stochastic processes and Lévy fluctuation theory.
Methodology
The authors bridge the gap between discrete-time observations and continuous-time analytical tools through a multi-step framework:
1. Phase-Type (PH) Distributions and MAPs
The study assumes that observations follow Phase-Type (PH) distributions, a versatile class capable of approximating any positive distribution. The log-likelihood ratio, which drives the CUSUM statistic, is modeled as a Markov Additive Process (MAP). In this bivariate process, a "modulator" (Markov chain) governs the behavior of an "ordinator" (the additive component), allowing for the modeling of non-i.i.d. data where states might be hidden.
2. Continuous-Time Embedding
A pivotal technique in this work is the construction of a continuous-time "generalized Sparre-Andersen process." By carefully aligning jump times, the authors ensure that the continuous-time process perfectly matches the discrete-time CUSUM statistic at specific intervals. This embedding allows for the application of powerful fluctuation theory identities to a discrete-time problem.
3. The Scale Matrix Expansion
The core mathematical innovation is a new series expansion formula for the scale matrix of a MAP. In fluctuation theory, the scale matrix is essential for solving first-passage problems (e.g., determining when a process first crosses a threshold). Previously, computing this matrix was a significant computational bottleneck. The authors provide a robust, series-based approach that makes these calculations feasible even for high-dimensional systems.
Numerical Validation
To demonstrate the efficacy of the proposed method, the authors conducted extensive numerical experiments. Using Python's mpmath library for 30-digit precision, they compared their exact analytical results against Monte Carlo simulations involving 100,000 sample paths. The results confirmed that the scale matrix method provides high-precision values consistent with simulation averages but without the inherent statistical noise.
Key Results and Insights
- Exact Performance Metrics: The paper derives explicit formulas for the Average Run Length (ARL), Average Detection Delay (ADD), and False Alarm Probability (PFA).
- Robustness: The framework is shown to be robust against non-i.i.d. observations, a common challenge in real-world applications where data may be modulated by hidden states.
- Barrier Optimization: The exactness of the formulas allows for precise determination of the optimal threshold barrier, balancing detection speed against false alarm rates more effectively than approximation-based methods.
Conclusion and Future Work
This research represents a significant advancement in sequential analysis, providing a computationally feasible path to exact CUSUM metrics. While the current framework assumes exponential tilting for post-change distributions and focuses on one-sided jumps, it sets the stage for future extensions. Potential directions include generalizing the jump structure and optimizing matrix exponential computations for real-time deployment.
Summary updated