Asymptotic Optimality in Bayesian Changepoint Detection Problems under Global False Alarm Probability Constraint

A. G. Tartakovskii

Teoriâ veroâtnostej i ee primeneniâ, Tome 53 (2008) no. 3, pp. 472-499

Résumé

In the 1960s Shiryaev developed the Bayesian theory of changepoint detection in independent and identically distributed (i.i.d.) sequences. In Shiryaev's classical setting the goal is to minimize an average delay to detection under the constraint imposed on the average probability of false alarm. Recently, Tartakovsky and Veeravalli [Theory Probab. Appl., 49 (2005), pp. 458–497] developed a general Bayesian asymptotic changepoint detection theory (in the classical setting) that is not limited to a restrictive i.i.d. assumption. It was proved that Shiryaev's detection procedure is asymptotically optimal under traditional average false alarm probability constraint, assuming that this probability is small. In the present paper, we consider a less conventional approach where the constraint is imposed on the global, supremum false alarm probability. An asymptotically optimal Bayesian change detection procedure is proposed and thoroughly evaluated for both i.i.d. and non-i.i.d. models when the global false alarm probability approaches zero.

Détail

Keywords: asymptotic optimality, changepoint detection, cumulative sum procedure, global false alarm probability, nonlinear renewal theory, Shiryaev's rule, sequential detection.

Bibliographie

[1] Assaf D., Pollak M., Ritov Y., Yakir B., “Detecting a change of a normal mean by dynamic sampling with a probability bound on a false alarm”, Ann. Statist., 21:3 (1993), 1155–1165 | DOI | MR | Zbl

[2] Baron M., Tartakovsky A. G., “Asymptotic optimality of change-point detection schemes in general continuous-time models”, Sequential Anal., 25:3 (2006), 257–296 | MR | Zbl

[3] Basseville M., Nikiforov I. V., Detection of Abrupt Changes: Theory and Applications, Prentice Hall, Englewood Cliffs, 1993, 528 pp. | MR

[4] Baum L. E., Katz M., “Convergence rates in the law of large numbers”, Trans. Amer. Math. Soc., 120 (1965), 108–123 | DOI | MR | Zbl

[5] Beibel M., “A note on Ritov's Bayes approach to the minimax property of the cusum procedure”, Ann. Statist., 24:4 (1996), 1804–1812 | DOI | MR | Zbl

[6] Beibel M., “Sequential detection of signals with known shape and unknown magnitude”, Statist. Sinica, 10:3 (2000), 715–729 | MR | Zbl

[7] Borovkov A. A., “Asimptoticheski optimalnye resheniya v zadache o razladke”, Teoriya veroyatn. i ee primen., 43:4 (1998), 625–654 | MR | Zbl

[8] Dragalin V. P., Tartakovsky A. G., Veeravalli V. V., “Multihypothesis sequential probability ratio tests. I: Asymptotic optimality”, IEEE Trans. Inform. Theory, 45:7 (1999), 2448–2461 | DOI | MR | Zbl

[9] Fuh C. D., “SPRT and CUSUM in hidden Markov models”, Ann. Statist., 31:3 (2003), 942–977 | DOI | MR | Zbl

[10] Fuh C. D., “Asymptotic operating characteristics of an optimal change point detection in hidden Markov models”, Ann. Statist., 32:5 (2004), 2305–2339 | DOI | MR | Zbl

[11] Gut A., Stopped Random Walks, Springer-Verlag, New York, 1988, 199 pp. | MR

[12] Hsu P. L., Robbins H., “Complete convergence and the law of large numbers”, Proc. Natl. Acad. Sci. USA, 33 (1947), 25–31 | DOI | MR | Zbl

[13] Lai T. L., “On $r$-quick convergence and a conjecture of Strassen”, Ann. Probab., 4:4 (1976), 612–627 | DOI | MR | Zbl

[14] Lai T. L., “Asymptotic optimality of invariant sequential probability ratio tests”, Ann. Statist., 9:2 (1981), 318–333 | DOI | MR | Zbl

[15] Lai T. L., “Sequential changepoint detection in quality control and dynamical systems”, J. Roy. Statist. Soc. Ser. B, 57:4 (1995), 613–658 | MR | Zbl

[16] Lai T. L., “Information bounds and quick detection of parameter changes in stochastic systems”, IEEE Trans. Inform. Theory, 44:7 (1998), 2917–2929 | DOI | MR | Zbl

[17] Lorden G., “Procedures for reacting to a change in distribution”, Ann. Math. Statist., 42 (1971), 1897–1908 | DOI | MR | Zbl

[18] Mei Y., Asymptotically optimal methods for sequential change-point detection, Ph. D. Thesis, California Institute of Technology, Pasadena, 2003 http://resolver.caltech.edu/CaltechETD:etd-05292003-133431

[19] Moustakides G. V., “Optimal stopping times for detecting changes in distributions”, Ann. Statist., 14:4 (1986), 1379–1387 | DOI | MR | Zbl

[20] Peskir G., Shiryaev A. N., Optimal Stopping and Free-Boundary Problems, Birkhäuser, Basel, 2006, 500 pp. | MR | Zbl

[21] Pollak M., “Optimal detection of a change in distribution”, Ann. Statist., 13:1 (1985), 206–227 | DOI | MR | Zbl

[22] Ritov Y., “Decision theoretic optimality of the CUSUM procedure”, Ann. Statist., 18:3 (1990), 1464–1469 | DOI | MR | Zbl

[23] Shiryaev A. N., “Obnaruzhenie spontanno voznikayuschikh effektov”, Dokl. AN SSSR, 138:4 (1961), 799–801

[24] Shiryaev A. N., “Ob optimalnykh metodakh v zadachakh skoreishego obnaruzheniya”, Teoriya veroyatn. i ee primen., 8:1 (1963), 26–51 | MR | Zbl

[25] Shiryaev A. N., Statisticheskii posledovatelnyi analiz, Nauka, M., 1976, 272 pp. | MR | Zbl

[26] Shiryaev A. N., “Minimaksnaya optimalnost metoda kumulyativnykh summ (CUSUM) v sluchae nepreryvnogo vremeni”, Uspekhi matem. nauk, 51:4 (1996), 173–174 | MR | Zbl

[27] Siegmund D., Sequential Analysis, Springer-Verlag, New York, 1985, 272 pp. | MR

[28] Tartakovskii A. G., Posledovatelnye metody v teorii informatsionnykh sistem, Radio i svyaz, M., 1991, 280 pp.

[29] Tartakovskii A. G., “Asimptoticheskie minimaksnoe mnogoalternativnoe pravilo obnaruzheniya razladki”, Tr. MIAN, 202, 1993, 287–295 | MR

[30] Tartakovsky A. G., “Asymptotic optimality of certain multihypothesis sequential tests: Non-i.i.d. case”, Statist. Inference Stoch. Process., 1:3 (1998), 265–295 | DOI | Zbl

[31] Tartakovsky A. G., Extended asymptotic optimality of certain change-point detection procedures, Preprint/Technical Report, University of Southern California, Los Angeles, 1998 | MR

[32] Tartakovsky A. G., “Asymptotic performance of a multichart CUSUM test under false alarm probability constraint”, Proc. 44th IEEE Conf. on Decision and Control and the European Control Conf. (CDC-ECC'05, Seville, Spain), 2005, 320–325, Omnipress CD-ROM

[33] Tartakovskii A. G., Ivanova I. A., “Sravnenie nekotorykh posledovatelnykh pravil obnaruzheniya razladki”, Problemy peredachi informatsii, 28:2 (1992), 21–29 | MR

[34] Tartakovsky A. G., Rozovskii B. L., Blažek R. B., Kim H., “Detection of intrusions in information systems by sequential change-point methods”, Statist. Methodol., 3:3 (2006), 252–293 | DOI | MR

[35] Tartakovsky A. G., Veeravalli V. V., “Change-point detection in multichannel and distributed systems”, Applied Sequential Methodologies, Dekker, New York, 2004, 339–370 | MR | Zbl

[36] Tartakovsky A. G., Veeravalli V. V., “General asymptotic Bayesian theory of quickest change detection”, Teoriya veroyatn. i ee primen., 49:3 (2004), 538–582 | MR | Zbl

[37] Woodroofe M., Nonlinear Renewal Theory in Sequential Analysis, SIAM, Philadelphia, 1982, 119 pp. | MR

[38] Yakir B., “Optimal detection of a change in distribution when the observations form a Markov chain with a finite state space”, Change-Point Problems, Inst. Math. Statist., Hayward, 1994, 346–358 | MR | Zbl