Tracking Stopping Times Through Noisy Observations

DOI10.1109/TIT.2008.2008115zbMATH Open1367.94117arXivmath/0701261MaRDI QIDQ4975706

Publication date: 8 August 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: A novel quickest detection setting is proposed which is a generalization of the well-known Bayesian change-point detection model. Suppose {(X_i,Y_i)}_{igeq 1} is a sequence of pairs of random variables, and that S is a stopping time with respect to {X_i}_{igeq 1}. The problem is to find a stopping time T with respect to {Y_i}_{igeq 1} that optimally tracks S, in the sense that T minimizes the expected reaction delay E(T-S)^+, while keeping the false-alarm probability P(T<S) below a given threshold alpha in [0,1]. This problem formulation applies in several areas, such as in communication, detection, forecasting, and quality control. Our results relate to the situation where the X_i's and Y_i's take values in finite alphabets and where S is bounded by some positive integer kappa. By using elementary methods based on the analysis of the tree structure of stopping times, we exhibit an algorithm that computes the optimal average reaction delays for all alpha in [0,1], and constructs the associated optimal stopping times T. Under certain conditions on {(X_i,Y_i)}_{igeq 1} and S, the algorithm running time is polynomial in kappa.

Full work available at URL: https://arxiv.org/abs/math/0701261

Mathematics Subject Classification ID

Detection theory in information and communication theory (94A13)