NDLI: Quickest Search Over Multiple Sequences

Content Provider	IEEE Xplore Digital Library
Author	Lifeng Lai Poor, H.V. Yan Xin Georgiadis, G.
Copyright Year	1963
Abstract	The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distribution Q₁ by searching over multiple sequences, some of which are drawn from Q₁ and the others of which are drawn from a different distribution Q₀, is considered. In the problem considered, the number of sequences with distribution Q₁ 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 Q₁ . 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.
Sponsorship	IEEE Information Theory Society
Starting Page	5375
Ending Page	5386
Page Count	12
File Size	579805
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Markov processes Error probability Optimization Delay Testing Switches Search problems sequential analysis Bayesian CUSUM optimal stopping quickest search
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quickest Change Detection of a Markov Process Across a Sensor Array

The Sample Complexity of Search Over Multiple Populations

Bayesian sequential composite hypothesis testing in discrete time

Asymptotically Optimal Quickest Change Detection In Multistream Data - Part 1: General Stochastic Models

Quickest detection in coupled systems

Sequential Detection and Identification of a Change in the Distribution of a Markov-Modulated Random Sequence

Minimax Robust Quickest Change Detection

Sequential Tracking of a Hidden Markov Chain Using Point Process Observations

Multisource Bayesian sequential change detection

Quickest Search Over Multiple Sequences

Similar Documents

Quickest Change Detection of a Markov Process Across a Sensor Array

The Sample Complexity of Search Over Multiple Populations

Bayesian sequential composite hypothesis testing in discrete time

Asymptotically Optimal Quickest Change Detection In Multistream Data - Part 1: General Stochastic Models

Quickest detection in coupled systems

Sequential Detection and Identification of a Change in the Distribution of a Markov-Modulated Random Sequence

Minimax Robust Quickest Change Detection

Sequential Tracking of a Hidden Markov Chain Using Point Process Observations

Multisource Bayesian sequential change detection

Quickest Search Over Multiple Sequences