×

Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis. (English) Zbl 1428.62370

Summary: A weighted Shiryaev-Roberts change detection procedure is shown to approximately minimize the expected delay to detection as well as higher moments of the detection delay among all change-point detection procedures with the given low maximal local probability of a false alarm within a window of a fixed length in pointwise and minimax settings for general non-i.i.d. data models and for the composite post-change hypothesis when the post-change parameter is unknown. We establish very general conditions for models under which the weighted Shiryaev-Roberts procedure is asymptotically optimal. These conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the “change” and “no-change” hypotheses, and we also provide sufficient conditions for a large class of ergodic Markov processes. Examples related to multivariate Markov models where these conditions hold are given.

MSC:

62L10 Sequential statistical analysis
62L15 Optimal stopping in statistics
60G40 Stopping times; optimal stopping problems; gambling theory
60J05 Discrete-time Markov processes on general state spaces
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baron, M.; Tartakovsky, A. G., Asymptotic optimality of change-point detection schemes in general continuous-time models, Sequential Anal., 25, 257-296 (2006), Invited Paper in Memory of Milton Sobel · Zbl 1136.62054
[2] Basseville, M.; Nikiforov, I. V., Detection of Abrupt Changes — Theory and Application, Information and System Sciences Series (1993), Prentice-Hall, Inc: Prentice-Hall, Inc Englewood Cliffs, NJ, USA, http://www.irisa.fr/sisthem/kniga/ [Online] · Zbl 1407.62012
[3] Feigin, P.; Tweedie, R., Random coefficient autoregressive processes: A Markov chain analysis of stationarity and finiteness of moments, J. Time Series Anal., 6, 1-14 (1985) · Zbl 0572.62069
[4] Fellouris, G.; Tartakovsky, A. G., Almost optimal sequential tests of discrete composite hypotheses, Statist. Sinica, 23, 1717-1741 (2013) · Zbl 1417.62228
[5] Fuh, C.-D., SPRT and CUSUM in hidden Markov models, Ann. Statist., 31, 942-977 (2003) · Zbl 1036.60005
[6] Galthouk, L.; Pergamenshchikov, S., Uniform concentration inequality for ergodic diffusion processes observed at discrete times, Stochastic Process. Appl., 123, 91-109 (2013) · Zbl 1266.60139
[7] Galthouk, L.; Pergamenshchikov, S., Geometric ergodicity for classes of homogeneous Markov chains, Stochastic Process. Appl., 124, 3362-3391 (2014) · Zbl 1323.60091
[8] Girshick, M. A.; Rubin, H., A Bayes approach to a quality control model, Ann. Math. Stat., 23, 114-125 (1952) · Zbl 0046.35405
[9] Hawkins, D. M.; Olwell, D. H., (Cumulative Sum Charts and Charting for Quality Improvement. Cumulative Sum Charts and Charting for Quality Improvement, Series in Statistics for Engineering and Physical Sciences (1998), Springer-Verlag: Springer-Verlag USA) · Zbl 0990.62537
[10] Klüppelberg, C.; Pergamenshchikov, S., The tail of the stationary distribution of a random coefficient AR(q) process with applications to an ARCH(q) process, Ann. Appl. Probab., 14, 971-1005 (2004) · Zbl 1094.62114
[11] Lai, T. L., Information bounds and quick detection of parameter changes in stochastic systems, IEEE Trans. Inform. Theory, 44, 2917-2929 (1998) · Zbl 0955.62084
[12] Lorden, G., Procedures for reacting to a change in distribution, Ann. Math. Stat., 42, 1897-1908 (1971) · Zbl 0255.62067
[13] Mason, R. L.; Young, J. C., Multivariate Statistical Process Control with Industrial Application (2001), SIAM: SIAM Philadelphia, PA, USA
[14] Mei, Y., Is average run length to false alarm always an informative criterion?, Sequential Anal., 27, 354-376 (2008) · Zbl 1149.62070
[15] Moustakides, G. V., Optimal stopping times for detecting changes in distributions, Ann. Statist., 14, 1379-1387 (1986) · Zbl 0612.62116
[16] Moustakides, G. V.; Polunchenko, A. S.; Tartakovsky, A. G., Numerical comparison of CUSUM and Shiryaev-Roberts procedures for detecting changes in distributions, Comm. Statist. Theory Methods, 38, 3225-3239 (2009) · Zbl 1175.62084
[17] Pergamenchtchikov, S.; Tartakovsky, A. G., Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data, Stat. Inference Stoch. Process., 21, 217-259 (2018) · Zbl 06860591
[18] Pollak, M.; Tartakovsky, A. G., Asymptotic exponentiality of the distribution of first exit times for a class of Markov processes with applications to quickest change detection, Theory Probab. Appl., 53, 430-442 (2009) · Zbl 1201.60073
[19] Pollak, M.; Tartakovsky, A. G., Optimality properties of the Shiryaev-Roberts procedure, Statist. Sinica, 19, 1729-1739 (2009) · Zbl 05629283
[20] Polunchenko, A. S.; Sokolov, G.; Tartakovsky, A. G., Optimal design and analysis of the exponentially weighted moving average chart for exponential data, Sri Lankan J. Appl. Stat., 15, 57-80 (2014), Special Issue: Modern Statistical Methodologies in the Cutting Edge of Science
[21] Polunchenko, A. S.; Tartakovsky, A. G., On optimality of the Shiryaev-Roberts procedure for detecting a change in distribution, Ann. Statist., 38, 3445-3457 (2010) · Zbl 1204.62141
[22] Shiryaev, A. N., On optimum methods in quickest detection problems, Theory Probab. Appl., 8, 22-46 (1963) · Zbl 0213.43804
[23] Srivastava, M. S.; Wu, Y., Comparison of EWMA CUSUM and Shiryayev-Roberts procedures for detecting a shift in the mean, Ann. Statist., 21, 645-670 (1993) · Zbl 0816.62068
[24] Tartakovsky, A. G., Asymptotic performance of a multichart CUSUM test under false alarm probability constraint, (Proceedings of the 44th IEEE Conference Decision and Control and European Control Conference, CDC-ECC’05, Seville, SP (2005), IEEE, Omnipress CD-ROM), 320-325
[25] Tartakovsky, A. G., Discussion on “Is average run length to false alarm always an informative criterion?” by Yajun Mei, Sequential Anal., 27, 396-405 (2008) · Zbl 1247.60060
[26] Tartakovsky, A. G., On asymptotic optimality in sequential changepoint detection: Non-iid case, IEEE Trans. Inform. Theory, 63, 3433-3450 (2017) · Zbl 1369.94378
[27] Tartakovsky, A. G., Asymptotic optimality of mixture rules for detecting changes in general stochastic models, IEEE Trans. Inform. Theory, 65, 1413-1429 (2019) · Zbl 1432.62275
[28] Tartakovsky, A. G.; Nikiforov, I. V.; Basseville, M., Sequential Analysis: Hypothesis Testing and Changepoint Detection, Monographs on Statistics and Applied Probability (2014), Chapman & Hall/CRC Press: Chapman & Hall/CRC Press Boca Raton, London, New York
[29] Tartakovsky, A. G.; Pollak, M.; Polunchenko, A. S., Third-order asymptotic optimality of the generalized Shiryaev-Roberts changepoint detection procedures, Theory Probab. Appl., 56, 457-484 (2012) · Zbl 1417.62232
[30] Tartakovsky, A. G.; Veeravalli, V. V., General asymptotic Bayesian theory of quickest change detection, Theory Probab. Appl., 49, 458-497 (2005) · Zbl 1131.62314
[31] Yakir, B., A note on the run length to false alarm of a change-point detection policy, Ann. Statist., 23, 272-281 (1995) · Zbl 0828.62072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.