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

By Cheng-Der Fuh. 2004

66 citations recorded by the source corpus.

Let ξ 0 , ξ 1 ,..., ξ ω-1 be observations from the hidden Markov model with probability distribution P θ0 , and let ξ ω , ξ ω+1 ,... be observations from the hidden Markov model with probability distribution P θ1 . The parameters θ 0 and θ 1 are given, while the change point ω is unknown. The problem is to raise an alarm as soon as possible after the distribution changes from P θ0 to P θ1 , but to avoid false alarms. Specifically, we seek a stopping rule N which allows us to observe the ξ's sequentially, such that E∞N is large, and subject to this constraint, sup k E k (N - k|N ≥ k) is as small as possible. Here E k denotes expectation under the change point k, and E∞ denotes expectation under the hypothesis of no change whatever. In this paper we investigate the performance of the Shiryayev-Roberts-Pollak (SRP) rule for change point detection in the dynamic system of hidden Markov models. By making use of Markov chain representation for the likelihood function, the structure of asymptotically minimax policy and of the Bayes rule, and sequential hypothesis testing theory for Markov random walks, we show that the SRP procedure is asymptotically minimax in the sense of Pollak [Ann. Statist. 13 (1985) 206-227]. Next, we present a second-order asymptotic approximation for the expected stopping time of such a stopping scheme when w = 1. Motivated by the sequential analysis in hidden Markov models, a nonlinear renewal theory for Markov random walks is also given.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fd7033f62965e41c58458a1f37ea6a3e70a2f3be

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

On Upper-Confidence Bound Policies for Switching Bandit Problems (2011, methodology): “Motivated by the problems cited above, and following a paradigm widely used in the change-point detection literature (see [12, 21] and references therein), we focus on non-stationary environments where the distributions of the rewards undergo abrupt changes.”
Asymptotic Optimality of Change-Point Detection Schemes in General Continuous-Time Models (2006, methodology): “The asymptotic theory that we developed relies upon the strong law of large numbers for the log-likelihood ratio process and the rates of convergence in the strong law similar to those used by Hsu and Robbins (1947) and later by Baum and Katz (1965), Strassen (1967), and Lai (1976) that lead to the ”