Minimax and pointwise sequential changepoint detection and identification for general stochastic models. (English) Zbl 1520.62101
Summary: This paper considers the problem of joint change detection and identification assuming multiple composite post-change hypotheses. We propose a multihypothesis changepoint detection-identification procedure that controls the probabilities of false alarm and wrong identification. We show that the proposed procedure is asymptotically minimax and pointwise optimal, minimizing moments of the detection delay as probabilities of false alarm and wrong identification approach zero. The asymptotic optimality properties hold for general stochastic models with dependent and nonidentically distributed observations. We illustrate general results for detection-identification of changes in multistream Markov ergodic processes. We consider several examples, including an application to rapid detection-identification of COVID-19 in Italy. Our proposed sequential algorithm allows much faster detection of COVID-19 than standard methods.
MSC:
| 62L10 | Sequential statistical analysis |
| 62L15 | Optimal stopping in statistics |
| 60G40 | Stopping times; optimal stopping problems; gambling theory |
| 62M02 | Markov processes: hypothesis testing |
| 60J05 | Discrete-time Markov processes on general state spaces |
| 62P10 | Applications of statistics to biology and medical sciences; meta analysis |
Keywords:
asymptotic optimality; changepoint detection; composite post-change hypotheses; detection and localization of epidemics; quickest change detection-identificationReferences:
| [1] | Dayanik, S.; Powell, W. B.; Yamazaki, K., Asymptotically optimal Bayesian sequential change detection and identification rules, Ann. Oper. Res., 208, 337-370 (2013) · Zbl 1365.62322 |
| [2] | Fuh, C.-D.; Tartakovsky, A. G., Asymptotic Bayesian theory of quickest change detection for hidden Markov models, IEEE Trans. Inf. Theory, 65, 511-529 (2019) · Zbl 1432.62278 |
| [3] | Galthouk, L.; Pergamenshchikov, S., Uniform concentration inequality for ergodic diffusion processes observed at discrete times, Stoch. Process. Appl., 123, 91-109 (2013) · Zbl 1266.60139 |
| [4] | Galthouk, L.; Pergamenshchikov, S., Geometric ergodicity for classes of homogeneous Markov chains, Stoch. Process. Appl., 124, 3362-3391 (2014) · Zbl 1323.60091 |
| [5] | Girardin, V.; Konev, V.; Pergamenshchikov, S. M., Kullback-Leibler approach to CUSUM quickest detection rule for Markovian time series, Sequential Anal., 37, 322-341 (2018) · Zbl 1431.62378 |
| [6] | 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 |
| [7] | Lai, T. L., Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems, IEEE Trans. Inf. Theory, 46, 595-608 (2000) · Zbl 0994.62078 |
| [8] | Meyn, S.; Tweedie, R., Markov Chains and Stochastic Stability (1993), Springer Verlag: Springer Verlag Berlin, New York · Zbl 0925.60001 |
| [9] | Nikiforov, I. V., A generalized change detection problem, IEEE Trans. Inf. Theory, 41, 171-187 (1995) · Zbl 0826.93064 |
| [10] | Nikiforov, I. V., A simple recursive algorithm for diagnosis of abrupt changes in random signals, IEEE Trans. Inf. Theory, 46, 2740-2746 (2000) · Zbl 1002.94514 |
| [11] | Nikiforov, I. V., A lower bound for the detection/isolation delay in a class of sequential tests, IEEE Trans. Inf. Theory, 49, 3037-3046 (2003) · Zbl 1301.94035 |
| [12] | 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 |
| [13] | Pergamenchtchikov, S.; Tartakovsky, A. G., Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis, J. Multivariate Anal., 174, 1-20 (2019) · Zbl 1428.62370 |
| [14] | Tartakovsky, A. G., Multidecision quickest change-point detection: Previous achievements and open problems, Sequential Anal., 27, 201-231 (2008) · Zbl 1274.62540 |
| [15] | Tartakovsky, A. G., (Sequential Change Detection and Hypothesis Testing: General Non-I.I.D. Stochastic Models and Asymptotically Optimal Rules. Sequential Change Detection and Hypothesis Testing: General Non-I.I.D. Stochastic Models and Asymptotically Optimal Rules, Monographs on Statistics and Applied Probability, vol. 165 (2020), Chapman & Hall/CRC Press, Taylor & Francis Group: Chapman & Hall/CRC Press, Taylor & Francis Group Boca Raton, London, New York) · Zbl 1430.62004 |
| [16] | Tartakovsky, A., An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models, IEEE Trans. Inf. Theory, 67, 4768-4783 (2021) · Zbl 1475.62223 |
| [17] | Tartakovsky, A. G.; Nikiforov, I. V.; Basseville, M., (Sequential Analysis: Hypothesis Testing and Changepoint Detection. Sequential Analysis: Hypothesis Testing and Changepoint Detection, Monographs on Statistics and Applied Probability, vol. 136 (2015), Chapman & Hall/CRC Press, Taylor & Francis Group: Chapman & Hall/CRC Press, Taylor & Francis Group Boca Raton, London, New York) · Zbl 1341.62026 |
| [18] | Yu, X.; Baron, M.; Choudhary, P. K., Change-point detection in binomial thinning processes, with applications in epidemiology, Sequential Anal., 32, 350-367 (2013) · Zbl 1294.62174 |
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.
