A series expansion formula of the scale matrix with applications in change-point detection

Jevgeņijs Ivanovs, Kazutoshi Yamazaki

Abstract

We introduce a new Levy fluctuation theoretic method to analyze 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. We develop a novel series expansion formula of the scale matrix for Markov additive processes of finite activity, and apply it to derive exact expressions of the average run length, average detection delay, and false alarm probability under the CUSUM procedure.

Introduction: The Challenge of Exact Change-Point Detection

In critical domains such as cyber-security, epidemiology, and signal processing, detecting a "change-point"—the moment a system transitions from a normal to an altered state—is vital. The Cumulative Sum (CUSUM) procedure is widely regarded as the optimal method for this task due to its efficiency in minimizing detection delays.

Despite its popularity, precisely analyzing CUSUM performance in discrete time has remained a significant challenge. Practitioners typically rely on Wald’s approximations or asymptotic results, which offer only estimates. This research addresses this gap by providing a framework for calculating exact values for key performance metrics:

  • Average Run Length (ARL): The expected time until an alarm is triggered.
  • Average Detection Delay (ADD): The speed at which a true change is identified.
  • False Alarm Probability (PFA): The risk of triggering an alarm when no change has occurred.

Methods: Bridging Statistics and Lévy Fluctuation Theory

The researchers propose a novel approach that connects statistical change-point detection with Lévy fluctuation theory. This methodology is built upon three foundational pillars:

  1. Phase-Type (PH) Distributions: The model assumes observations follow PH distributions. Because PH distributions are dense, they can approximate virtually any positive distribution, offering high flexibility.
  2. Markov Additive Processes (MAPs): By employing exponential tilting to characterize the post-change distribution, the authors demonstrate that the CUSUM statistic can be modeled as a reflected MAP. A MAP is a bivariate process where an ordinator component evolves like a Lévy process, governed by a background Markov chain known as the modulator.
  3. Scale Matrix Series Expansion: The "Scale Matrix" $W(x)$ is essential for analyzing MAPs but is notoriously difficult to compute. The authors derived a new series expansion formula that represents the scale matrix as a sum of matrix exponentials. This breakthrough makes solving first-passage problems computationally feasible.
Comparison of discrete-time and continuous-time CUSUM processes under varying drift conditions, demonstrating the first-passage threshold crossings (red stars).

Key Insights: CUSUM as a Reflected Process

A central insight of this work is the realization that the CUSUM statistic is essentially a reflected version of a log-likelihood ratio process. By framing this in continuous time as a "generalized Sparre-Andersen process," the authors could leverage powerful tools from fluctuation theory.

Unlike previous methodologies limited to specific cases (e.g., Erlang distributions), this new formula is applicable to any MAP with finite activity and one-sided jumps. Furthermore, the paper extends the traditional i.i.d. (independent and identically distributed) assumption to non-i.i.d. settings using Hidden Markov Models, allowing for more robust evaluations when real-world data deviates from theoretical assumptions.

Key Results and Validation

The primary contribution is the derivation of explicit, exact formulas for ARL, ADD, and PFA.

  • Validation: Numerical experiments using synthetic Phase-Type distributions and 100,000 Monte Carlo simulations confirmed that the analytical formulas match simulated results perfectly.
  • Computational Efficiency: Using high-precision arithmetic (via the mpmath library), the series expansion provides accurate results even when the scale matrix grows exponentially.
  • Optimal Barrier Selection: This method enables practitioners to determine the optimal alarm threshold with far greater precision than traditional approximation-based methods.

Limitations and Future Directions

While a significant advancement, the method has some constraints:

  • Numerical Stability: The exponential growth of the scale matrix necessitates high-precision software (30+ digits), as standard 64-bit floats may be insufficient for large thresholds.
  • Jump Directionality: The current expansion is optimized for processes with one-sided jumps (spectrally negative or positive). Extending this to two-sided jumps remains a future challenge.
  • Complexity: As the Phase-Type distribution or background Markov chain grows in complexity, the matrix size increases, potentially leading to computational bottlenecks.

Beyond change-point detection, this new scale matrix formula holds promise for applications in insurance mathematics (ruin theory) and queueing analysis.

Summary updated

Abstract

We introduce a new Levy fluctuation theoretic method to analyze 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. We develop a novel series expansion formula of the scale matrix for Markov additive processes of finite activity, and apply it to derive exact expressions of the average run length, average detection delay, and false alarm probability under the CUSUM procedure.
BibTeX
@misc{ivanovs2021series,
  author = {Jevgeņijs Ivanovs and Kazutoshi Yamazaki},
  title = {{A series expansion formula of the scale matrix with applications in change-point detection}},
  year = {2021},
  eprint = {2109.03361},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.03361},
}
Figure