Multidecision Quickest Change-Point Detection: Previous Achievements and Open Problems

Abstract

The following multidecision quickest detection problem, which is of importance for a variety of applications, is considered. There are N populations that are either statistically identical or where the change occurs in one of them at an unknown point in time. Alternatively, there may be N “isolated” points/hypotheses associated with a change. It is necessary to detect the change in distribution as soon as possible and indicate which population is “corrupted” or which hypothesis is true after a change occurs. Both the false alarm rate and misidentification rate should be controlled by given (usually low) levels. We discuss performance of natural multihypothesis/multipopulation generalizations of the Page and Shiryaev-Roberts procedures, including certain asymptotically optimal properties of these tests when both the false alarm and the misidentification rates are low. Specifically, we show that under certain conditions the proposed multihypothesis detection-identification procedures asymptotically minimize the trade-off between any positive moment of the detection lag and the false alarm/misclassification rates in the worst-case scenario. At the same time, the corresponding sequential detection-identification procedures are computationally simple and can be easily implemented online in a variety of applications such as rapid detection of intrusions in large-scale distributed computer networks, target detection in cluttered environment, and detection of terrorist' malicious activity. Limitations of the existing and proposed solutions to this challenging problem are also discussed.

Keywords:

• Asymptotic optimality
• Average detection delay
• False alarm rate
• Misidentification rate
• Moments of the detection delay
• Multidecision change-point detection
• Multihypothesis sequential tests
• Slippage problems

Subject Classification:

• 62L15
• 60G40
• 62F12
• 62F15

ACKNOWLEDGMENTS

The research was supported in part by U.S.\ Office of Naval Research Grants N00014-99-1-0068 and N00014-95-1-0229 and by U.S.\ Army Research Office MURI Grant W911NF-06-1-0094 at the University of Southern California. We would like to thank Alexey Polunchenko for the help in Monte Carlo simulations.

Notes

Recommended by Nitis Mukhopadhyay