Asymptotic operating characteristics of an optimal change point detection in hidden Markov models (Q1766136)

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.