Geodesic
General asymptotic Bayesian theory of
Teoriâ veroâtnostej i ee primeneniâ, Tome 49 (2004) no. 3, pp. 538-582 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The optimal detection procedure for detecting changes in independent and identically distributed (i.i.d.) sequences in a Bayesian setting was derived by Shiryaev in the 1960s sixties. However, the analysis of the performance of this procedure in terms of the average detection delay and false alarm probability has been an open problem. In this paper, we develop a general asymptotic change-point detection theory that is not limited to a restrictive i.i.d. assumption. In particular, we investigate the performance of the Shiryaev procedure for general discrete-time stochastic models in the asymptotic setting, where the false alarm probability approaches zero. We show that the Shiryaev procedure is asymptotically optimal in the general non-i.i.d. case under mild conditions. We also show that the two popular non-Bayesian detection procedures, namely the Page and the Shiryaev–Roberts–Pollak procedures, are generally not optimal (even asymptotically) under the Bayesian criterion. The results of this study are shown to be especially important in studying the asymptotics of decentralized change detection procedures.
Keywords: change-point detection, sequential detection, asymptotic optimality, nonlinear renewal theory. 
@article{TVP_2004_49_3_a6,
     author = {A. G. Tartakovskii and V. Veeravalli},
     title = {General asymptotic {Bayesian} theory of},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {538--582},
     year = {2004},
     volume = {49},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TVP_2004_49_3_a6/}
}
TY  - JOUR
AU  - A. G. Tartakovskii
AU  - V. Veeravalli
TI  - General asymptotic Bayesian theory of
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2004
SP  - 538
EP  - 582
VL  - 49
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TVP_2004_49_3_a6/
LA  - en
ID  - TVP_2004_49_3_a6
ER  - 
%0 Journal Article
%A A. G. Tartakovskii
%A V. Veeravalli
%T General asymptotic Bayesian theory of
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2004
%P 538-582
%V 49
%N 3
%U http://geodesic.mathdoc.fr/item/TVP_2004_49_3_a6/
%G en
%F TVP_2004_49_3_a6
A. G. Tartakovskii; V. Veeravalli. General asymptotic Bayesian theory of. Teoriâ veroâtnostej i ee primeneniâ, Tome 49 (2004) no. 3, pp. 538-582. http://geodesic.mathdoc.fr/item/TVP_2004_49_3_a6/

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

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

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

[4] Blažek R., Kim H., Rozovskii B., Tartakovsky A., “A novel approach to detection of “denial-of-service” attacks via adaptive sequential and batch-sequential change-point detection methods”, Proceedings of the IEEE Systems, Man, and Cybernetics Information Assurance Workshop (West Point, NY), 2001

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

[6] Chow Y. S., Lai T. L., “Some one-sided theorems on the tail distribution of sample sums with application to the last time and largest excess of boundary crossings”, Trans. Amer. Math. Soc., 208 (1975), 51–72 | DOI | MR | Zbl

[7] Dragalin V. P., “Optimalnost obobschennogo algoritma kumulyativnykh summ v zadache skoreishego obnaruzheniya razladki”, Trudy MIAN, 202, 1993, 132–148 | 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] Gut A., Stopped Random Walks: Limit Theorems and Applications, Springer-Verlag, New York, 1988, 199 pp. | MR

[11] 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

[12] Kent S., “On the trial of intrusions into information systems”, IEEE Spectrum, 37:12 (2000), 52–56 | DOI

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

[19] Page E. S., “Continuous inspection schemes”, Biometrika, 41 (1954), 100–115 | MR | Zbl

[20] Peskir G., Shiryaev A. N., “Solving the Poisson disorder problem”, Advances in Finance and Stochastics, Essays in honour of Dieter Sondermann, eds. K. Sandmann et al., Springer-Verlag, Berlin, 2002, 295–312 | MR | Zbl

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

[22] Pollak M., “Average run lengths of an optimal method of detecting a change in distribution”, Ann. Statist., 15:2 (1987), 749–779 | DOI | MR | Zbl

[23] Pollak M., Siegmund D., “A diffusion process and its applications to detecting a change in the drift of Brownian motion”, Biometrika, 72:2 (1985), 267–280 | DOI | MR | Zbl

[24] Poor H. V., An Introduction to Signal Detection and Estimation, Springer-Verlag, New York, 1994, 398 pp. | MR

[25] Shiryaev A. N., “Obnaruzhenie spontanno voznikayuschikh effektov”, Dokl. AN SSSR, 138:4 (1961), 1039–1042 | Zbl

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

[27] Shiryaev A. N., Statisticheskii posledovatelnyi analiz. Optimalnye pravila ostanovki, Nauka, M., 1976, 272 pp. | MR | Zbl

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

[29] Siegmund D., Sequential Analysis: Tests and Confidence Intervals, Springer-Verlag, New York, 1985, 272 pp. | MR

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

[31] Tartakovsky A. G., “Asymptotic properties of CUSUM and Shiryaev's procedures for detecting a change in a nonhomogeneous Gaussian process”, Math. Methods Statist., 4:4 (1995), 389–404 | MR | Zbl

[32] Tartakovskii A. G., “Asimptoticheski minimaksnoe mnogoalternativnoe posledovatelnoe pravilo obnaruzheniya razladki”, Trudy MIAN, 202, 1993, 287–295 | MR | Zbl

[33] 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

[34] Tartakovsky A. G., Extended asymptotic optimality of certain change-point detection procedures, Preprint, Center for Applied Mathematical Sciences, University of Southern California, Los Angeles, 2003

[35] Tartakovsky A. G., Veeravalli V. V., “An efficient sequential procedure for detecting changes in multichannel and distributed systems”, Proceeding of the Fifth International Conference on Information Fusion (Annapolis, MD, 2002), Omnipress, 2002, 41–48

[36] Tartakovsky A. G., Veeravalli V. V., “Asymptotic analysis of Bayesian quickest change detection procedures”, Proceedings of the International Symposium on Information Theory (Lausanne, 2002), 217

[37] Tartakovsky A. G., Veeravalli V. V., “Asymptotics of quickest change detection procedures under a Bayesian criterion”, Proceedings of the Information Theory Workshop (Bangalore, 2002), 100–103

[38] Tartakovsky A. G., Veeravalli V. V., “Quickest change detection in distributed sensor systems”, Proceedings of the Sixth International Conference on Information Fusion (Cairns, 2003), 756–763

[39] Tartakovsky A. G., Veeravalli V. V., “Change-point detection in multichannel and distributed systems with applications”, Applications of Sequential Methodologies, eds. N. Mukhopadhyay, S. Datta, and S. Chattopadhyay, Dekker, New York, 331–363 | MR

[40] Tsitsiklis J. N., “Extremal properties of likelihood-ratio quantizers”, IEEE Trans. Commun., 41:4 (1993), 550–558 | DOI | MR | Zbl

[41] Veeravalli V. V., “Decentralized quickest change detection”, IEEE Trans. Inform. Theory, IT-47:4 (2001), 1657–1665 | DOI | MR

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

[43] Yakir B., “Optimal detection of a change in distribution when the observations form a Markov chain with a finite state space”, Change-Point Problems, IMS Lecture Notes Monogr. Ser., 23, eds. E. Carlstein, H. Muller, and D. Siegmund, Inst. Math. Statist., Hayward, CA, 1994, 346–358 | MR | Zbl

[44] Yakir B., “A note on optimal detection of a change in distribution”, Ann. Statist., 25:5 (1997), 2117–2126 | DOI | MR | Zbl