Quickest Search Over Correlated Sequences with Model Uncertainty

Abstract

An ordered set of data sequences is given where, broadly, the data sequences are categorized into normal and abnormal ones. The normal sequences consist of random variables generated according to a known distribution, while there exist uncertainties about the distributions of the abnormal sequences. Moreover, the generations of different sequences are correlated, induced by an underlying physical coupling, where a sequence being normal or abnormal depends on the status of the rest of the sequences according to a known dependency kernel. The objective is to design the quickest sequential and data-adaptive sampling procedure for identifying one abnormal sequence. This quickest search strategy strikes a balance between the quality and agility of the search process, as two opposing figures of merit. This paper characterizes the sampling and search strategy. Motivated by the fact that full characterization of such strategies can become computationally prohibitive, this paper also proposes asymptotically optimal sampling and search strategies that are computationally efficient.