TY - JOUR

T1 - Quickest search over multiple sequences

AU - Lai, Lifeng

AU - Poor, H. Vincent

AU - Xin, Yan

AU - Georgiadis, Georgios

N1 - Funding Information:
Manuscript received February 16, 2010; revised December 23, 2010; accepted April 22, 2011. Date of current version July 29, 2011. The work of L. Lai and H. V. Poor was supported by the Qatar National Research Fund under Grant NPRP-08-522-2-211. The material in this paper was presented in part at the International Workshop on Applied Probability, Madrid, Spain, July 2010. L. Lai is with the Department of Systems Engineering, University of Arkansas, Little Rock, AR 72204 USA (e-mail: lxlai@ualr.edu). H. V. Poor is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: poor@princeton.edu). Y. Xin is with the NEC Laboratories America, Inc., Princeton, NJ 08540 USA (e-mail: yanxin@nec-labs.com). G. Georgiadis is with the Computer Science Department, University of California, Los Angeles, CA 90095 USA (e-mail: giorgos@cs.ucla.edu). Communicated by F. Hlawatsch, Associate Editor for Detection and Estimation. Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2011.2159038

PY - 2011/8

Y1 - 2011/8

N2 - The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distribution Q1 by searching over multiple sequences, some of which are drawn from Q 1 and the others of which are drawn from a different distribution Q0, is considered. In the problem considered, the number of sequences with distribution Q1 is assumed to be a random variable whose value is unknown. Within a Bayesian formulation, a sequential decision rule is derived that optimizes a trade-off between the probability of false alarm and the number of samples needed for the decision. In the case in which one can observe one sequence at a time, it is shown that the cumulative sum (CUSUM) test, which is well-known to be optimal for a non-Bayesian statistical change-point detection formulation, is optimal for the problem under study. Specifically, the CUSUM test is run on the first sequence. If a reset event occurs in the CUSUM test, then the sequence under examination is abandoned and the rule switches to the next sequence. If the CUSUM test stops, then the rule declares that the sequence under examination when the test stops is generated by Q1. The result is derived by assuming that there are infinitely many sequences so that a sequence that has been examined once is not retested. If there are finitely many sequences, the result is also valid under a memorylessness condition. Expressions for the performance of the optimal sequential decision rule are also developed. The general case in which multiple sequences can be examined simultaneously is considered. The optimal solution for this general scenario is derived.

AB - The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distribution Q1 by searching over multiple sequences, some of which are drawn from Q 1 and the others of which are drawn from a different distribution Q0, is considered. In the problem considered, the number of sequences with distribution Q1 is assumed to be a random variable whose value is unknown. Within a Bayesian formulation, a sequential decision rule is derived that optimizes a trade-off between the probability of false alarm and the number of samples needed for the decision. In the case in which one can observe one sequence at a time, it is shown that the cumulative sum (CUSUM) test, which is well-known to be optimal for a non-Bayesian statistical change-point detection formulation, is optimal for the problem under study. Specifically, the CUSUM test is run on the first sequence. If a reset event occurs in the CUSUM test, then the sequence under examination is abandoned and the rule switches to the next sequence. If the CUSUM test stops, then the rule declares that the sequence under examination when the test stops is generated by Q1. The result is derived by assuming that there are infinitely many sequences so that a sequence that has been examined once is not retested. If there are finitely many sequences, the result is also valid under a memorylessness condition. Expressions for the performance of the optimal sequential decision rule are also developed. The general case in which multiple sequences can be examined simultaneously is considered. The optimal solution for this general scenario is derived.

KW - Bayesian

KW - CUSUM

KW - optimal stopping

KW - quickest search

KW - sequential analysis

UR - http://www.scopus.com/inward/record.url?scp=79960974281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960974281&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2159038

DO - 10.1109/TIT.2011.2159038

M3 - Review article

AN - SCOPUS:79960974281

SN - 0018-9448

VL - 57

SP - 5375

EP - 5386

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 8

M1 - 5961845

ER -