×

zbMATH — the first resource for mathematics

Minimax optimal sequential hypothesis tests for Markov processes. (English) Zbl 1460.62131
The paper deals with a generalization of the Kiefer and Weiss problem of constructing a sequential test that, in addition to meeting the targeted error probabilities under the hypotheses, minimizes the maximum expected run length over all feasible distributions [A. Dvoretzky et al., Ann. Math. Stat. 24, 254–264 (1953; Zbl 0050.14803); J. Kiefer and L. Weiss, Ann. Math. Stat. 28, 57–74 (1957; Zbl 0079.35406)].
A well-established drawback of sequential hypothesis tests is that their higher efficiency depends critically on the assumption that the process generating the observations indeed follows the assumed model. In the paper, under mild assumptions, sufficient conditions for strict minimax optimality of sequential tests for multiple hypotheses under distributional uncertainty are derived. The design of optimal sequential tests for simple hypotheses is revisited, and it is shown that the partial derivatives of the corresponding cost function are closely related to the performance metrics of the underlying sequential test. An implicit characterization of the least favorable distributions for a given testing policy is stated. By combining the results on optimal sequential tests and least favorable distributions, sufficient conditions for a sequential test to be minimax optimal under general distributional uncertainties are obtained. Numerical examples for minimax optimal sequential tests under different uncertainties illustrate the theoretical results.
MSC:
62L10 Sequential statistical analysis
62C20 Minimax procedures in statistical decision theory
62F35 Robustness and adaptive procedures (parametric inference)
62M02 Markov processes: hypothesis testing
Software:
robustbase
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Avella Medina, M. and Ronchetti, E. (2015). Robust statistics: A selective overview and new directions. Wiley Interdiscip. Rev.: Comput. Stat. 7 372-393.
[2] Banerjee, T. and Veeravalli, V. V. (2015). Data-efficient minimax quickest change detection with composite post-change distribution. IEEE Trans. Inform. Theory 61 5172-5184. Zentralblatt MATH: 1359.94218
Digital Object Identifier: doi:10.1109/TIT.2015.2458864
· Zbl 1359.94218
[3] Basu, A., Harris, I. R., Hjort, N. L. and Jones, M. C. (1998). Robust and efficient estimation by minimising a density power divergence. Biometrika 85 549-559. Zentralblatt MATH: 0926.62021
Digital Object Identifier: doi:10.1093/biomet/85.3.549
· Zbl 0926.62021
[4] Breuer, T. and Csiszár, I. (2016). Measuring distribution model risk. Math. Finance 26 395-411. · Zbl 1348.91290
[5] Brodsky, B. and Darkhovsky, B. (2008). Minimax methods for multihypothesis sequential testing and change-point detection problems. Sequential Anal. 27 141-173. Zentralblatt MATH: 1274.62512
Digital Object Identifier: doi:10.1080/07474940801989111
· Zbl 1274.62512
[6] Brodsky, B. E. and Darkhovsky, B. S. (2008). Minimax sequential tests for many composite hypotheses. I. Theory Probab. Appl. 52 565-579. Zentralblatt MATH: 1148.62064
Digital Object Identifier: doi:10.1007/s11203-006-9004-6
· Zbl 1148.62064
[7] Capasso, V. and Bakstein, D. (2015). An Introduction to Continuous-Time Stochastic Processes: Theory, Models, and Applications to Finance, Biology, and Medicine, 3rd ed. Modeling and Simulation in Science, Engineering and Technology. Birkhäuser/Springer, New York. Zentralblatt MATH: 1333.60002
· Zbl 1333.60002
[8] Choquet, G. (1954). Theory of capacities. Ann. Inst. Fourier (Grenoble) 5 131-295. Zentralblatt MATH: 0064.35101
Digital Object Identifier: doi:10.5802/aif.53
· Zbl 0064.35101
[9] DeGroot, M. H. (1960). Minimax sequential tests of some composite hypotheses. Ann. Math. Stat. 31 1193-1200. Zentralblatt MATH: 0104.12303
Digital Object Identifier: doi:10.1214/aoms/1177705690
Project Euclid: euclid.aoms/1177705690
· Zbl 0104.12303
[10] Dragalin, V. P. and Novikov, A. A. (1987). Asymptotic solution of the Kiefer-Weiss problem for processes with independent increments. Theory Probab. Appl. 32 617-627. Zentralblatt MATH: 0716.62076
Digital Object Identifier: doi:10.1137/1132094
· Zbl 0716.62076
[11] Dvoretzky, A., Kiefer, J. and Wolfowitz, J. (1953). Sequential decision problems for processes with continuous time parameter. Testing hypotheses. Ann. Math. Stat. 24 254-264. Zentralblatt MATH: 0050.14803
Digital Object Identifier: doi:10.1214/aoms/1177729031
Project Euclid: euclid.aoms/1177729031
· Zbl 0050.14803
[12] El-Sawy, A. H. and VandeLinde, V. D. (1979). Robust sequential detection of signals in noise. IEEE Trans. Inform. Theory 25 346-353. Zentralblatt MATH: 0414.94001
Digital Object Identifier: doi:10.1109/TIT.1979.1056049
· Zbl 0414.94001
[13] Fauß, M. (2016). Design and analysis of optimal and minimax robust sequential hypthesis tests. Ph.D. thesis, TU Darmstadt, Institute of Communications.
[14] Fauß, M. and Zoubir, A. M. (2015). A linear programming approach to sequential hypothesis testing. Sequential Anal. 34 235-263. · Zbl 1317.62065
[15] Fauß, M. and Zoubir, A. M. (2016). Old bands, new tracks—Revisiting the band model for robust hypothesis testing. IEEE Trans. Signal Process. 64 5875-5886. Zentralblatt MATH: 1414.94193
Digital Object Identifier: doi:10.1109/TSP.2016.2600505
· Zbl 1414.94193
[16] Fauß, M., Zoubir, A. M. and Poor, V. H. (2018). On the equivalence of \(f\)-divergence balls and density bands in robust detection. In Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).
[17] Fauß, M., Zoubir, A. M. and Poor, H. V. (2020). Supplement to “Minimax optimal sequential hypothesis tests for Markov processes.” https://doi.org/10.1214/19-AOS1899SUPP.
[18] Fellouris, G. and Tartakovsky, A. G. (2012). Nearly minimax one-sided mixture-based sequential tests. Sequential Anal. 31 297-325. Zentralblatt MATH: 1273.62189
· Zbl 1273.62189
[19] Fellouris, G. and Tartakovsky, A. G. (2013). Almost optimal sequential tests of discrete composite hypotheses. Statist. Sinica 23 1717-1741. Zentralblatt MATH: 1417.62228
· Zbl 1417.62228
[20] Ferrari, S. and Stengel, R. F. (2005). Smooth function approximation using neural networks. IEEE Trans. Neural Netw. 16 24-38.
[21] Gao, R., Xie, L., Xie, Y. and Xu, H. (2018). Robust hypothesis testing using Wasserstein uncertainty sets. Adv. Neural Inf. Process. Syst. 7913-7923.
[22] Ghosh, B. K. and Sen, P. K., eds. (1991) Handbook of Sequential Analysis. Statistics: Textbooks and Monographs 118. Dekker, New York.
[23] Gül, G. and Zoubir, A. M. (2016). Robust hypothesis testing with \(\alpha \)-divergence. IEEE Trans. Signal Process. 64 4737-4750. · Zbl 1414.94228
[24] Györfi, L. and Nemetz, T. (1975). On the dissimilarity of probability measures. Technical report, Mathematical Institute of the Hungarian Academy of Science. · Zbl 0435.62008
[25] Györfi, L. and Nemetz, T. (1977). \(f\)-dissimilarity: A general class of separation measures of several probability measures. In Topics in Information Theory (Second Colloq., Keszthely, 1975). Colloq. Math. Soc. János Bolyai 16 309-321. · Zbl 0362.60017
[26] Györfi, L. and Nemetz, T. (1978). \(f\)-dissimilarity: A generalization of the affinity of several distributions. Ann. Inst. Statist. Math. 30 105-113. · Zbl 0453.62014
[27] Hafner, R. (1993). Construction of minimax-tests for bounded families of probability-densities. Metrika 40 1-23. Zentralblatt MATH: 0798.62056
Digital Object Identifier: doi:10.1007/BF02613659
· Zbl 0798.62056
[28] Hazewinkel, M., ed. (1994). Kolmogorov-Chapman equation. In Encyclopaedia of Mathematics 5 292. Springer, Dordrecht, Netherlands.
[29] Huber, P. J. (1965). A robust version of the probability ratio test. Ann. Math. Stat. 36 1753-1758. Mathematical Reviews (MathSciNet): MR185747
Zentralblatt MATH: 0137.12702
Digital Object Identifier: doi:10.1214/aoms/1177699803
Project Euclid: euclid.aoms/1177699803
· Zbl 0137.12702
[30] Huber, P. J. (1981). Robust Statistics. Wiley, Hoboken, NJ. Zentralblatt MATH: 0536.62025
· Zbl 0536.62025
[31] Huber, P. J. and Strassen, V. (1973). Minimax tests and the Neyman-Pearson lemma for capacities. Ann. Statist. 1 251-263. Zentralblatt MATH: 0259.62008
Digital Object Identifier: doi:10.1214/aos/1176342363
Project Euclid: euclid.aos/1176342363
· Zbl 0259.62008
[32] Kassam, S. A. (1981). Robust hypothesis testing for bounded classes of probability densities. IEEE Trans. Inform. Theory 27 242-247. Zentralblatt MATH: 0495.62041
Digital Object Identifier: doi:10.1109/TIT.1981.1056314
· Zbl 0495.62041
[33] Kassam, S. A. and Poor, H. V. (1985). Robust techniques for signal processing: A survey. Proc. IEEE 73 433-481. Zentralblatt MATH: 0569.62084
Digital Object Identifier: doi:10.1109/PROC.1985.13167
· Zbl 0569.62084
[34] Kharin, A. (2002). On robustifying of the sequential probability ratio test for a discrete model under “contaminations”. Aust. J. Stat. 31 267-277.
[35] Kiefer, J. and Weiss, L. (1957). Some properties of generalized sequential probability ratio tests. Ann. Math. Stat. 28 57-74. Zentralblatt MATH: 0079.35406
Digital Object Identifier: doi:10.1214/aoms/1177707037
Project Euclid: euclid.aoms/1177707037
· Zbl 0079.35406
[36] Kunsch, R. (2017). High-dimensional function approximation: Breaking the curse with Monte Carlo methods. Ph.D. thesis, Friedrich-Schiller-Universität Jena, Jena, Germany.
[37] Lorden, G. (1976). \(2\)-SPRT’s and the modified Kiefer-Weiss problem of minimizing an expected sample size. Ann. Statist. 4 281-291. Zentralblatt MATH: 0367.62099
Digital Object Identifier: doi:10.1214/aos/1176343407
Project Euclid: euclid.aos/1176343407
· Zbl 0367.62099
[38] Maronna, R. A., Martin, R. D. and Yohai, V. J. (2006). Robust Statistics: Theory and Methods. Wiley Series in Probability and Statistics. Wiley, Chichester. Zentralblatt MATH: 1094.62040
· Zbl 1094.62040
[39] Maurice, R. J. (1957). A minimax procedure for choosing between two populations using sequential sampling. J. Roy. Statist. Soc. Ser. B 19 255-261. Zentralblatt MATH: 0103.12203
Digital Object Identifier: doi:10.1111/j.2517-6161.1957.tb00261.x
· Zbl 0103.12203
[40] Nguyen, X., Wainwright, M. J. and Jordan, M. I. (2009). On surrogate loss functions and \(f\)-divergences. Ann. Statist. 37 876-904. Zentralblatt MATH: 1162.62060
Digital Object Identifier: doi:10.1214/08-AOS595
Project Euclid: euclid.aos/1236693153
· Zbl 1162.62060
[41] Novikov, A. (2009). Optimal sequential multiple hypothesis tests. Kybernetika (Prague) 45 309-330. Mathematical Reviews (MathSciNet): MR2518154
Zentralblatt MATH: 1167.62453
· Zbl 1167.62453
[42] Österreicher, F. (1978). On the construction of least favourable pairs of distributions. Z. Wahrsch. Verw. Gebiete 43 49-55. · Zbl 0371.62011
[43] Papageorgiou, N. S. (1997). Convex integral functionals. Trans. Amer. Math. Soc. 349 1421-1436. Zentralblatt MATH: 0962.47029
Digital Object Identifier: doi:10.1090/S0002-9947-97-01478-5
· Zbl 0962.47029
[44] Pardo, L. (2006). Statistical Inference Based on Divergence Measures. Statistics: Textbooks and Monographs 185. CRC Press/CRC, Boca Raton, FL.
[45] Pavlov, I. V. (1991). A sequential procedure for testing composite hypotheses with application to the Kiefer-Weiss problem. Theory Probab. Appl. 35 280-292. Zentralblatt MATH: 0723.62043
Digital Object Identifier: doi:10.1137/1135036
· Zbl 0723.62043
[46] Poor, H. V. (1980). Robust decision design using a distance criterion. IEEE Trans. Inform. Theory 26 575-587. Zentralblatt MATH: 0445.62017
Digital Object Identifier: doi:10.1109/TIT.1980.1056249
· Zbl 0445.62017
[47] Poor, H. V. and Hadjiliadis, O. (2009). Quickest Detection. Cambridge Univ. Press, Cambridge. Zentralblatt MATH: 1271.62015
· Zbl 1271.62015
[48] Reid, M. D. and Williamson, R. C. (2011). Information, divergence and risk for binary experiments. J. Mach. Learn. Res. 12 731-817. Zentralblatt MATH: 1280.68192
· Zbl 1280.68192
[49] Rockafellar, R. T. (1968). Integrals which are convex functionals. Pacific J. Math. 24 525-539. Zentralblatt MATH: 0159.43804
Digital Object Identifier: doi:10.2140/pjm.1968.24.525
· Zbl 0159.43804
[50] Rockafellar, R. T. (1970). Convex Analysis. Princeton Mathematical Series 28. Princeton Univ. Press, Princeton, NJ.
[51] Rudin, W. (1976). Principles of Mathematical Analysis, 3rd ed. International Series in Pure and Applied Mathematics. McGraw-Hill, New York-Auckland-Düsseldorf. · Zbl 0346.26002
[52] Schmitz, N. (1987). Minimax sequential tests of composite hypotheses on the drift of a Wiener process. Stat. Hefte 28 247-261. Zentralblatt MATH: 0647.62079
Digital Object Identifier: doi:10.1007/BF02932605
· Zbl 0647.62079
[53] Siegmund, D. (1985). Sequential Analysis: Tests and Confidence Intervals. Springer Series in Statistics. Springer, New York. Zentralblatt MATH: 0573.62071
· Zbl 0573.62071
[54] Sochman, J. and Matas, J. (2005). WaldBoost—Learning for time constrained sequential detection. In Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (C. Schmid, S. Soatto and C. Tomasi, eds.) 150-156.
[55] Tartakovsky, A., Nikiforov, I. and Basseville, M. (2015). Sequential Analysis: Hypothesis Testing and Changepoint Detection. Monographs on Statistics and Applied Probability 136. CRC Press, Boca Raton, FL. Zentralblatt MATH: 1341.62026
· Zbl 1341.62026
[56] Tartakovsky, A. G., Li, X. R. and Yaralov, G. (2003). Sequential detection of targets in multichannel systems. IEEE Trans. Inform. Theory 49 425-445. Zentralblatt MATH: 1063.94518
Digital Object Identifier: doi:10.1109/TIT.2002.807288
· Zbl 1063.94518
[57] Unnikrishnan, J., Veeravalli, V. V. and Meyn, S. P. (2011). Minimax robust quickest change detection. IEEE Trans. Inform. Theory 57 1604-1614. Zentralblatt MATH: 1366.94154
Digital Object Identifier: doi:10.1109/TIT.2011.2104993
· Zbl 1366.94154
[58] Varshney, K. R. (2011). Bayes risk error is a Bregman divergence. IEEE Trans. Signal Process. 59 4470-4472. Zentralblatt MATH: 1392.94667
Digital Object Identifier: doi:10.1109/TSP.2011.2159500
· Zbl 1392.94667
[59] Verdú, S. and Poor, H. V. (1984). On minimax robustness: A general approach and applications. IEEE Trans. Inform. Theory 30 328-340. · Zbl 0544.93064
[60] Vos, H. J. (2001). A minimax procedure in the context of sequential testing problems in psychodiagnostics. Br. J. Math. Stat. Psychol. 54 139-159.
[61] Voudouri, E. and Kurz, L. (1988). A robust approach to sequential detection. IEEE Trans. Acoust. Speech Signal Process. 36 1200-1210. Zentralblatt MATH: 0850.93759
Digital Object Identifier: doi:10.1109/29.1649
· Zbl 0850.93759
[62] Wald, A. (1947). Sequential Analysis. Wiley, Hoboken, NJ. Zentralblatt MATH: 0029.15805
· Zbl 0029.15805
[63] Weiß, C. H. and Kim, H.-Y. (2013). Binomial \(\operatorname{AR}(1)\) processes: Moments, cumulants, and estimation. Statistics 47 494-510. · Zbl 1327.62477
[64] Weiß, C. H. and Kim, H.-Y. (2013). Parameter estimation for binomial \(\operatorname{AR}(1)\) models with applications in finance and industry. Statist. Papers 54 563-590. · Zbl 1307.62061
[65] Yilmaz, E., Gemmeke, J. F. and Hamme, H. V. (2016). Noise robust exemplar matching with alpha-beta divergence. Speech Commun. 76 127-142.
[66] Zhitlukhin, M. V., Muravlev, A. A. and Shiryaev, A. N. (2013). The optimal decision rule in the Kiefer-Weiss problem for a Brownian motion. Russian Math. Surveys 68 389-391. Zentralblatt MATH: 1284.62136
Digital Object Identifier: doi:10.1070/RM2013v068n02ABEH004834
· Zbl 1284.62136
[67] Zoubir, A. M., Koivunen, V., Chakhchoukh, Y. and Muma, M. (2012). Robust estimation in signal processing: A tutorial-style treatment of fundamental concepts. IEEE Signal Process. Mag. 29 61-80.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.