Universal scheme for optimal search and stop

Sirin Nitinawarat, Venugopal V. Veeravalli

Research output: Contribution to journalArticlepeer-review

Abstract

The problem of universal search and stop using an adaptive search policy is considered. When the unique target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal scheme for search and stop is proposed using only the knowledge of the absence distribution, and its asymptotic performance is analyzed. The universal test is shown to yield a vanishing error probability, and to achieve the optimal reliability when the target is present, universally for every target distribution. Consequently, it is established that the knowledge of the target distribution is only useful for improving the reliability for detecting that the target is missing. It is also shown that a multiplicative gain for the search reliability equal to the number of searched locations is achieved by allowing adaptivity in the search.

Original languageEnglish (US)
Pages (from-to)1759-1783
Number of pages25
JournalBernoulli
Volume23
Issue number3
DOIs
StatePublished - Aug 2017

Keywords

  • Search and stop
  • Sequential design of experiments
  • Sequential hypothesis testing

ASJC Scopus subject areas

  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Universal scheme for optimal search and stop'. Together they form a unique fingerprint.

Cite this