Consider a large number of detectors each generating a data
stream. The task is to detect online, distribution changes in a small
fraction of the data streams. Previous approaches to this problem
include the use of mixture likelihood ratios and sum of CUSUMs. We
provide here extensions and modifications of these approaches that
are optimal in detecting normal mean shifts. We show how the (optimal) detection delay depends on the fraction of data streams undergoing distribution changes as the number of detectors goes to infinity.
There are three detection domains. In the first domain for moderately
large fractions, immediate detection is possible. In the second domain for smaller fractions, the detection delay grows logarithmically
with the number of detectors, with an asymptotic constant extending those in sparse normal mixture detection. In the third domain
for even smaller fractions, the detection delay lies in the framework
of the classical detection delay formula of Lorden. We show that the
optimal detection delay is achieved by the sum of detectability score
transformations of either the partial scores or CUSUM scores of the
data streams.
Menu
