LAUSR

AbstractLet X1, X2,... be independent random variables observed sequentially and such that X1,..., Xθ−1 have a common probability density p0, while Xθ, Xθ+1,... are all distributed according to p1 ≠ p0. It is assumed that p0 and p1 are known, but the time change θ ∈ ℤ+ is unknown and the goal is to construct a stopping time τ that detects the change-point θ as soon as possible. The standard approaches to this problem rely essentially on some prior information about θ. For instance, in the Bayes approach, it is assumed that θ is a random variable with a known probability distribution. In the methods related to hypothesis testing, this a priori information is hidden in the so-called average run length. The main goal in this paper is to construct stopping times that are free from a priori information about θ. More formally, we propose an approach to solving approximately the following minimization problem: $$\Delta(\theta;{\tau^\alpha})\rightarrow\min_{\tau^\alpha}\;\;\text{subject}\;\text{to}\;\;\alpha(\theta;{\tau^\alpha})\leq\alpha\;\text{for}\;\text{any}\;\theta\geq1,$$Δ(θ;τα)→minταsubjecttoα(θ;τα)≤αforanyθ≥1,where α(θ; τ) = Pθ{τ < θ} is the false alarm probability and Δ(θ; τ) = Eθ(τ − θ)+ is the average detection delay computed for a given stopping time τ. In contrast to the standard CUSUM algorithm based on the sequential maximum likelihood test, our approach is related to a multiple hypothesis testing methods and permits, in particular, to construct universal stopping times with nearly Bayes detection delays.