×

State-of-the-art in sequential change-point detection. (English) Zbl 06124706

Summary: We provide an overview of the state-of-the-art in the area of sequential change-point detection assuming discrete time and known pre- and post-change distributions. The overview spans over all major formulations of the underlying optimization problem, namely, Bayesian, generalized Bayesian, and minimax. We pay particular attention to the latest advances in each. Also, we link together the generalized Bayesian problem with multi-cyclic disorder detection in a stationary regime when the change occurs at a distant time horizon. We conclude with two case studies to illustrate the cutting edge of the field at work.

MSC:

62L10 Sequential statistical analysis
60G40 Stopping times; optimal stopping problems; gambling theory
62C20 Minimax procedures in statistical decision theory
62F15 Bayesian inference
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atkinson K, Han W (2009) Theoretical numerical analysis: a functional analysis framework. In: Texts in applied mathematics, vol 39, 3rd edn. Springer doi: 10.1007/978-1-4419-0458-4 · Zbl 1181.47078
[2] Basseville M, Nikiforov IV (1993) Detection of abrupt changes: theory and application. Prentice Hall, Englewood Cliffs
[3] Brodsky BE, Darkhovsky BS (1993) Nonparameteric methods in change point problems. In: Mathematics and its applications, vol 243. Kluwer Academic Publishers
[4] Feinberg EA, Shiryaev AN (2006) Quickest detection of drift change for Brownian motion in generalized Bayesian and minimax settings. Stat Decis 24(4):445–470. doi: 10.1524/stnd.2006.24.4.445 · Zbl 1135.60024
[5] Ferguson TS (1967) Mathematical statistics–a decision theoretic approach. Academic Press, New York · Zbl 0153.47602
[6] Fuh CD (2003) SPRT and CUSUM in hidden Markov models. Ann Stat 31(3):942–977. doi: 10.1214/aos/1056562468 · Zbl 1036.60005 · doi:10.1214/aos/1056562468
[7] Fuh CD (2004) Asymptotic operating characteristics of an optimal change point detection in hidden Markov models. Ann Stat 32(5):2305–2339. doi: 10.1214/009053604000000580 · Zbl 1073.60047 · doi:10.1214/009053604000000580
[8] Girschick MA, Rubin H (1952) A Bayes approach to a quality control model. Ann Math Stat 23(1):114–125. doi: 10.1214/aoms/1177729489 · Zbl 0046.35405 · doi:10.1214/aoms/1177729489
[9] Harris TE (1963) The theory of branching processes. Springer-Verlag, Berlin · Zbl 0117.13002
[10] Kesten H (1973) Random difference equations and renewal theory for products of random matrices. Acta Math. 131(1):207–248. doi: 10.1007/BF02392040 · Zbl 0291.60029 · doi:10.1007/BF02392040
[11] Lai TL (1995) Sequential changepoint detection in quality control and dynamical systems. J R Stat Soc B 57(4):613–658 · Zbl 0832.62072
[12] Lai TL (1998) Information bounds and quick detection of parameter changes in stochastic systems. IEEE Trans Inf Theory 44:2917–2929. doi: 10.1109/18.737522 · Zbl 0955.62084 · doi:10.1109/18.737522
[13] Lorden G (1971) Procedures for reacting to a change in distribution. Ann Math Stat 42(6):1897–1908 · Zbl 0255.62067 · doi:10.1214/aoms/1177693055
[14] Mevorach Y, Pollak M (1991) A small sample size comparison of the Cusum and the Shiryayev-Roberts approaches to changepoint detection. Am J Math Manage Sci 11:277–298 · Zbl 0800.62503
[15] Moustakides GV (1986) Optimal stopping times for detecting changes in distributions. Ann Stat 14(4):1379–1387 · Zbl 0612.62116 · doi:10.1214/aos/1176350164
[16] Moustakides GV (2008) Sequential change detection revisited. Ann Stat 36(2):787–807. doi: 10.1214/009053607000000938 · Zbl 1133.62063 · doi:10.1214/009053607000000938
[17] Moustakides GV, Polunchenko AS, Tartakovsky AG (2011) A numerical approach to performance analysis of quickest change-point detection procedures. Stat Sin 21(2):571–596 · Zbl 1214.62084 · doi:10.5705/ss.2011.026a
[18] Page ES (1954) Continuous inspection schemes. Biometrika 41(1):100–115 · Zbl 0056.38002
[19] Pollak M (1985) Optimal detection of a change in distribution. Ann Stat 13(1):206–227 · Zbl 0573.62074 · doi:10.1214/aos/1176346587
[20] Pollak M (1987) Average run lengths of an optimal method of detecting a change in distribution. Ann Stat 15(2):749–779 · Zbl 0632.62080 · doi:10.1214/aos/1176350373
[21] Pollak M, Siegmund D (1986) Convergence of quasi-stationary to stationary distributions for stochastically monotone Markov processes. J Appl Probab 23(1):215–220 · Zbl 0595.60075 · doi:10.2307/3214131
[22] Pollak M, Tartakovsky AG (2009a) 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(3):430–442 · Zbl 1201.60073 · doi:10.1137/S0040585X97983742
[23] Pollak M, Tartakovsky AG (2009b) Optimality properties of the Shiryaev-Roberts procedure. Stat Sin 19:1729–1739 · Zbl 05629283
[24] Polunchenko AS, Tartakovsky AG (2010) On optimality of the Shiryaev-Roberts procedure for detecting a change in distribution. Ann Stat 36(6):3445–3457. doi: 10.1214/09-AOS775 · Zbl 1204.62141 · doi:10.1214/09-AOS775
[25] Poor HV, Hadjiliadis O (2008) Quickest detection. Cambridge University Press · Zbl 1271.62015
[26] Ritov Y (1990) Decision theoretic optimality of the CUSUM procedure. Ann Stat 18(3):1464–1469 · Zbl 0712.62073 · doi:10.1214/aos/1176347761
[27] Roberts S (1966) A comparison of some control chart procedures. Technometrics 8(3):411–430 · doi:10.1080/00401706.1966.10490374
[28] Shewhart WA (1931) Economic control of quality of manufactured product. D. Van Nostrand Company, Inc., New York
[29] Shiryaev AN (1961) The problem of the most rapid detection of a disturbance in a stationary process. Sov Math Dokl 2:795–799 · Zbl 0109.11201
[30] Shiryaev AN (1963) On optimum methods in quickest detection problems. Theory Probab Appl 8(1):22–46. doi: 10.1137/1108002 · Zbl 0213.43804 · doi:10.1137/1108002
[31] Shiryaev AN (1978) Optimal stopping rules. Springer-Verlag, New York · Zbl 0391.60002
[32] Shiryaev AN (2006) From ”disorder” to nonlinear filtering and martingale theory. In: Bolibruch A, Osipov Y, Sinai Y (eds) Mathematical events of the twentieth century. Springer Berlin Heidelberg, pp 371–397, doi: 10.1007/3-540-29462-7_18 · Zbl 1082.01010
[33] Shiryaev AN (2009) On the stochastic models and optimal methods in the quickest detection problems. Theory Probab Appl 53(3):385–401. doi: 10.1137/S0040585X97983717 · Zbl 1395.62249 · doi:10.1137/S0040585X97983717
[34] Shiryaev AN (2010) Quickest detection problems: fifty years later. Seq Anal 29:345–385. doi: 10.1080/07474946.2010520580 · Zbl 1203.62137 · doi:10.1080/07474946.2010.520580
[35] Siegmund D (1985) Sequential analysis: tests and confidence intervals. Springer Series in Statistics. Springer-Verlag, New York · Zbl 0573.62071
[36] Springer MD, Thompson WE (1970) The distribution of products of Beta, Gamma and Gaussian random variables. SIAM J Appl math 18(4):721–737. doi: 10.1137/0118065 · Zbl 0198.23703 · doi:10.1137/0118065
[37] Tartakovsky AG (1991) Sequential methods in the theory of information systems. Radio & Communications, Moscow, Russia
[38] Tartakovsky AG (2005) Asymptotic performance of a multichart CUSUM test under false alarm probability constraint. In: Proceedings of the 2005 IEEE Conference on Decision and Control, vol 44, pp 320–325
[39] Tartakovsky AG (2008) Discussion on ”Is average run length to false alarm always an informative criterion?” by Yajun Mei. Seq Anal 27(4):396–405. doi: 10.1080/07474940802446046 · Zbl 1247.60060 · doi:10.1080/07474940802446046
[40] Tartakovsky AG (2009a) Asymptotic optimality in Bayesian changepoint detection problems under global false alarm probability constraint. Theory Probab Appl 53:443–466. doi: 10.1137/S0040585X97983754 · Zbl 1395.62251 · doi:10.1137/S0040585X97983754
[41] Tartakovsky AG (2009b) Discussion on ”Optimal sequential surveillance for finance, public health, and other areas” by Marianne Frisén. Seq Anal 28(3):365–371. doi: 10.1080/07474940903041704 · Zbl 1274.62541 · doi:10.1080/07474940903041704
[42] Tartakovsky AG, Moustakides GV (2010) State-of-the-art in Bayesian changepoint detection. Seq Anal 29(2):125–145. doi: 10.1080/07474941003740997 · Zbl 1190.62151 · doi:10.1080/07474941003740997
[43] Tartakovsky AG, Polunchenko AS (2010) Minimax optimality of the Shiryaev-Roberts procedure. In: Proceedings of the 5th international workshop on applied probability, Universidad Carlos III of Madrid, Spain · Zbl 1204.62141
[44] Tartakovsky AG, Veeravalli VV (2005) General asymptotic Bayesian theory of quickest change detection. Theory Probab Appl 49(3):458–497. doi: 10.1137/S0040585X97981202 · Zbl 1131.62314 · doi:10.1137/S0040585X97981202
[45] Tartakovsky AG, Pollak M, Polunchenko AS (2008) Asymptotic exponentiality of first exit times for recurrent Markov processes and applications to changepoint detection. In: Proceedings of the 2008 International workshop on applied probability, Compiégne, France
[46] Tartakovsky AG, Polunchenko AS, Moustakides GV (2009) Design and comparison of Shiryaev–Roberts- and CUSUM-type change-point detection procedures. In: Proceedings of the 2nd International workshop in sequential methodologies, University of Technology of Troyes, Troyes, France
[47] Tartakovsky AG, Pollak M, Polunchenko AS (2011) Third-order asymptotic optimality of the generalized Shiryaev-Roberts changepoint detection procedures. Theoiya Veroyatnostej i ee Primeneniya 56(3) (in press) · Zbl 1417.62232
[48] Wald A (1947) Sequential analysis. J. Wiley & Sons, Inc., New York · Zbl 0041.26303
[49] Woodroofe M (1982) Nonlinear renewal theory in sequential analysis. Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0487.62062
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.