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

Fuh, Cheng-Der

Ann. Stat. 32, No. 5, 2305-2339 (2004).

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.

Reviewer: Wolfgang Stadje (Osnabrück)

MSC:

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)

Keywords:

asymptotic optimality; random matrices; Shiryaev-Roberts-Pollak rule

References:

[1]	Alsmeyer, G. (1994). On the Markov renewal theorem. Stochastic Process. Appl. 50 37–56. · Zbl 0789.60066 · doi:10.1016/0304-4149(94)90146-5
[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 · doi:10.1023/A:1022290807360
[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 · doi:10.1109/TIT.1986.1057160
[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 · doi:10.1214/ss/1028905933
[6]	Fuh, C.-D. (2003). SPRT and CUSUM in hidden Markov models. Ann. Statist. 31 942–977. · Zbl 1036.60005 · doi:10.1214/aos/1056562468
[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 · doi:10.1214/105051604000000260
[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 · doi:10.1239/jap/1032265205
[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 · doi:10.1239/aap/1005091358
[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 · doi:10.1016/S0304-4149(99)00104-0
[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 · doi:10.1007/BF01844607
[12]	Kesten, H. (1973). Random difference equations and renewal theory for products of random matrices. Acta Math. 131 207–248. · Zbl 0291.60029 · doi:10.1007/BF02392040
[13]	Kesten, H. (1974). Renewal theory for functionals of a Markov chain with general state space. Ann. Probab. 2 355–386. · Zbl 0303.60090 · doi:10.1214/aop/1176996654
[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 · doi:10.1109/18.737522
[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 · doi:10.1214/aos/1176343950
[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 · doi:10.1214/aos/1176344555
[19]	Lorden, G. (1971). Procedures for reacting to a change in distribution. Ann. Math. Statist. 41 1897–1908. · Zbl 0255.62067 · doi:10.1214/aoms/1177693055
[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 · doi:10.1137/1131073
[21]	Melfi, V. F. (1992). Nonlinear Markov renewal theory with statistical applications. Ann. Probab. 20 753–771. JSTOR: · Zbl 0756.60082 · doi:10.1214/aop/1176989804
[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 · doi:10.1214/aos/1176350164
[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 · doi:10.1016/0304-4149(86)90001-3
[25]	Pollak, M. (1985). Optimal detection of a change in distribution. Ann. Statist. 13 206–227. JSTOR: · Zbl 0573.62074 · doi:10.1214/aos/1176346587
[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 · doi:10.1214/aos/1176350373
[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 · doi:10.1214/aos/1176343284
[28]	Ritov, Y. (1990). Decision theoretic optimality of the CUSUM procedure. Ann. Statist. 18 1464–1469. JSTOR: · Zbl 0712.62073 · doi:10.1214/aos/1176347761
[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 · doi:10.1137/1108002
[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 · doi:10.1214/aop/1176996181
[34]	Woodroofe, M. (1977). Second order approximations for sequential point and interval estimation. Ann. Statist. 5 984–995. JSTOR: · Zbl 0374.62081 · doi:10.1214/aos/1176343953
[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 · doi:10.1214/aos/1069362390
[38]	Zhang, C.-H. (1988). A nonlinear renewal theory. Ann. Probab. 16 793–824. JSTOR: · Zbl 0643.60067 · doi:10.1214/aop/1176991788