An Accurate Method for Determining the Pre-Change Run Length Distribution of the Generalized Shiryaev-Roberts Detection Procedure

Abstract

Change-of-measure is a powerful technique in wide use across statistics, probability, and analysis. Particularly known as Wald's likelihood ratio identity, the technique enabled the proof of a number of exact and asymptotic optimality results pertaining to the problem of quickest change-point detection. Within the latter problem's context we apply the technique to develop a numerical method to compute the generalized Shiryaev–Roberts (GSR) detection procedure's pre-change run length distribution. Specifically, the method is based on the integral equations approach and uses the collocation framework with the basis functions chosen to exploit a certain change-of-measure identity and a specific martingale property of the GSR procedure's detection statistic. As a result, the method's accuracy and robustness improve substantially, even though the method's theoretical rate of convergence is shown to be merely quadratic. A tight upper bound on the method's error is supplied as well. The method is not restricted to a particular data distribution or to a specific value of the GSR detection statistic's head start. To conclude, we offer a case study to demonstrate the proposed method at work, drawing particular attention to the method's accuracy and its robustness with respect to three factors: (1) partition size (rough vs. fine), (2) change magnitude (faint vs. contrast), and (3) average run length (ARL) to false alarm level (low vs. high). Specifically, assuming independent standard Gaussian observations undergoing a surge in the mean, we employ the method to study the GSR procedure's run length's pre-change distribution, its average (i.e., the usual ARL to false alarm), and its standard deviation. As expected from the theoretical analysis, the method's high accuracy and robustness with respect to the foregoing three factors are confirmed experimentally. We also comment on extending the method to handle other performance measures and other procedures.

Keywords:

• Fredholm integral equations of the second kind
• Numerical analysis
• Sequential analysis
• Sequential change-point detection
• Shiryaev-Roberts procedure
• Shiryaev-Roberts-r procedure

Subject Classifications:

• 62L10
• 62L15
• 62P30
• 65R20

ACKNOWLEDGMENTS

The authors are thankful to Shelemyahu Zacks (SUNY Binghamton), Shyamal K. De (SUNY Binghamton), Sven Knoth (Helmut Schimdt University, Hamburg, Germany), and George V. Moustakides (University of Patras, Greece) for reading this work's preliminary draft and for providing valuable feedback that helped improve the article. The authors are also grateful to the Editor-in-Chief, Nitis Mukhopadhyay (University of Connecticut–Storrs), and to the anonymous reviewers whose comments helped to ameliorate the article further.

Notes

Recommended by Nitis Mukhopadhyay