Asymptotic operating characteristics of an optimal change point detection in hidden Markov models. (English) Zbl 1073.60047

A sequence of observations is considered which forms a hidden Markov model that changes its law at some unknown discrete time instant \(k\in \{1,2,\ldots, \infty\}\). The problem is to find a stopping rule \(N\) that minimizes \(\sup_{1\leq k < \infty} E(N-k\mid N\geq k)\) subject to \(E_\infty (N) \geq \gamma\) (for prespecified \(\gamma\)). The author shows that the Shiryaev-Roberts-Pollak (SRP) rule provides an asymptotically minimax sequence of stopping rules, meaning that it minimizes the supremum within order \(o(1)\) as \(\gamma \to \infty\). The key tools are a representation of the likelihood ratio used in the SRP rule as the ratio of \(L_1\)-norms of products of Markov random matrices, a Bayesian approach, and sequential testing theory for Markov random walks. The paper also presents a nonlinear renewal theory for Markov random walks. Finally, a second-order asymptotic expansion of the average run length in the case \(k=1\) is given.


60G40 Stopping times; optimal stopping problems; gambling theory
60J05 Discrete-time Markov processes on general state spaces
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI arXiv


[1] Alsmeyer, G. (1994). On the Markov renewal theorem. Stochastic Process. Appl. 50 37–56. · Zbl 0789.60066
[2] Alsmeyer, G. (2003). On the Harris recurrence of iterated random Lipschitz functions and related convergence rate results. J. Theoret. Probab. 16 217–247. · Zbl 1022.60067
[3] Bansal, R. K. and Papantoni-Kazakos, P. (1986). An algorithm for detecting a change in a stochastic process. IEEE Trans. Inform. Theory 32 227–235. · Zbl 0596.60040
[4] Basseville, M. and Nikiforov, I. V. (1993). Detection of Abrupt Changes : Theory and Application . Prentice Hall, Englewood Cliffs, NJ.
[5] Braun, J. V. and Müller, H. G. (1998). Statistical methods for DNA sequence segmentation. Statist. Sci. 13 142–162. · Zbl 0960.62121
[6] Fuh, C.-D. (2003). SPRT and CUSUM in hidden Markov models. Ann. Statist. 31 942–977. · Zbl 1036.60005
[7] Fuh, C.-D. (2004). Uniform Markov renewal theory and ruin probabilities in Markov random walks. Ann. Appl. Probab. 14 1202–1241. · Zbl 1052.60072
[8] Fuh, C.-D. and Lai, T. L. (1998). Wald’s equations, first passage times and moments of ladder variables in Markov random walks. J. Appl. Probab. 35 566–580. · Zbl 0922.60043
[9] Fuh, C.-D. and Lai, T. L. (2001). Asymptotic expansions in multidimensional Markov renewal theory and first passage times for Markov random walks. Adv. in Appl. Probab. 33 652–673. · Zbl 0995.60081
[10] Fuh, C.-D. and Zhang, C.-H. (2000). Poisson equation, maximal inequalities and \(r\)-quick convergence for Markov random walks. Stochastic Process. Appl. 87 53–67. · Zbl 1045.60074
[11] Götze, F. and Hipp, C. (1983). Asymptotic expansions for sums of weakly dependent random vectors. Z. Wahrsch. Verw. Gebiete 64 211–239. · Zbl 0497.60022
[12] Kesten, H. (1973). Random difference equations and renewal theory for products of random matrices. Acta Math. 131 207–248. · Zbl 0291.60029
[13] Kesten, H. (1974). Renewal theory for functionals of a Markov chain with general state space. Ann. Probab. 2 355–386. · Zbl 0303.60090
[14] Lai, T. L. (1995). Sequential change point detection in quality control and dynamical systems (with discussion). J. Roy. Statist. Soc. Ser. B 57 613–658. · Zbl 0832.62072
[15] Lai, T. L. (1998). Information bounds and quick detection of parameter changes in stochastic systems. IEEE Trans. Inform. Theory 44 2917–2929. · Zbl 0955.62084
[16] Lai, T. L. (2001). Sequential analysis: Some classical problems and new challenges (with discussion). Statist. Sinica 11 303–408. · Zbl 1037.62081
[17] Lai, T. L. and Siegmund, D. (1977). A nonlinear renewal theory with applications to sequential analysis. I. Ann. Statist. 5 946–954. JSTOR: · Zbl 0378.62069
[18] Lai, T. L. and Siegmund, D. (1979). A nonlinear renewal theory with applications to sequential analysis. II. Ann. Statist. 7 60–76. JSTOR: · Zbl 0409.62074
[19] Lorden, G. (1971). Procedures for reacting to a change in distribution. Ann. Math. Statist. 41 1897–1908. · Zbl 0255.62067
[20] Malinovskii, V. K. (1986). Asymptotic expansions in the central limit theorem for recurrent Markov renewal processes. Theory Probab. Appl. 31 523–526. · Zbl 0615.60020
[21] Melfi, V. F. (1992). Nonlinear Markov renewal theory with statistical applications. Ann. Probab. 20 753–771. JSTOR: · Zbl 0756.60082
[22] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, New York. · Zbl 0925.60001
[23] Moustakides, G. V. (1986). Optimal stopping times for detecting changes in distribution. Ann. Statist. 14 1379–1387. JSTOR: · Zbl 0612.62116
[24] Niemi, S. and Nummelin, E. (1986). On non-singular renewal kernels with an application to a semigroup of transition kernels. Stochastic Process. Appl. 22 177–202. · Zbl 0606.60080
[25] Pollak, M. (1985). Optimal detection of a change in distribution. Ann. Statist. 13 206–227. JSTOR: · Zbl 0573.62074
[26] Pollak, M. (1987). Average run lengths of an optimal method of detecting a change in distribution. Ann. Statist. 15 749–779. JSTOR: · Zbl 0632.62080
[27] Pollak, M. and Siegmund, D. (1975). Approximations to the expected sample size of certain sequential tests. Ann. Statist. 3 1267–1282. JSTOR: · Zbl 0347.62063
[28] Ritov, Y. (1990). Decision theoretic optimality of the CUSUM procedure. Ann. Statist. 18 1464–1469. JSTOR: · Zbl 0712.62073
[29] Roberts, S. W. (1966). A comparison of some control chart procedures. Technometrics 8 411–430.
[30] Shiryayev, A. N. (1963). On optimum methods in quickest detection problems. Theory Probab. Appl. 8 22–46. · Zbl 0213.43804
[31] Shiryayev, A. N. (1978). Optimum Stopping Rules. Springer, New York. · Zbl 0391.60002
[32] Siegmund, D. (1985). Sequential Analysis. Tests and Confidence Intervals. Springer, New York. · Zbl 0573.62071
[33] Woodroofe, M. (1976). A renewal theorem for curved boundaries and moments of first passage times. Ann. Probab. 4 67–80. · Zbl 0368.60099
[34] Woodroofe, M. (1977). Second order approximations for sequential point and interval estimation. Ann. Statist. 5 984–995. JSTOR: · Zbl 0374.62081
[35] Woodroofe, M. (1982). Nonlinear Renewal Theory in Sequential Analysis. SIAM, Philadelphia. · Zbl 0487.62062
[36] Yakir, B. (1994). Optimal detection of a change in distribution when the observations form a Markov chain with a finite state space. In Change-Point Problems (E. Carlstein, H. G. Müller and D. Siegmund, eds.) 346–358. IMS, Hayward, CA. · Zbl 1163.62340
[37] Yakir, B. (1997). A note on optimal detection of a change in distribution. Ann. Statist. 25 2117–2126. · Zbl 0942.62088
[38] Zhang, C.-H. (1988). A nonlinear renewal theory. Ann. Probab. 16 793–824. JSTOR: · Zbl 0643.60067
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.