Universal scheme for optimal search and stop

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of universal search and stop using an adaptive search policy is considered. When the target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal sequential 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 a missing target. 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)
Title of host publication2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages322-328
Number of pages7
ISBN (Electronic)9781479971954
DOIs
StatePublished - Oct 27 2015
EventInformation Theory and Applications Workshop, ITA 2015 - San Diego, United States
Duration: Feb 1 2015Feb 6 2015

Publication series

Name2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings

Other

OtherInformation Theory and Applications Workshop, ITA 2015
CountryUnited States
CitySan Diego
Period2/1/152/6/15

Fingerprint

Error probability

Keywords

  • Computational modeling
  • Error probability
  • Joints
  • Reliability
  • Search problems
  • Testing
  • Yttrium

ASJC Scopus subject areas

  • Computer Science Applications
  • Information Systems

Cite this

Nitinawarat, S., & Veeravalli, V. V. (2015). Universal scheme for optimal search and stop. In 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings (pp. 322-328). [7309008] (2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITA.2015.7309008

Universal scheme for optimal search and stop. / Nitinawarat, Sirin; Veeravalli, Venugopal Varadachari.

2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. p. 322-328 7309008 (2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Nitinawarat, S & Veeravalli, VV 2015, Universal scheme for optimal search and stop. in 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings., 7309008, 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 322-328, Information Theory and Applications Workshop, ITA 2015, San Diego, United States, 2/1/15. https://doi.org/10.1109/ITA.2015.7309008
Nitinawarat S, Veeravalli VV. Universal scheme for optimal search and stop. In 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc. 2015. p. 322-328. 7309008. (2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings). https://doi.org/10.1109/ITA.2015.7309008
Nitinawarat, Sirin ; Veeravalli, Venugopal Varadachari. / Universal scheme for optimal search and stop. 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 322-328 (2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings).
@inproceedings{7d42bc893985479c96c5036fefa83109,
title = "Universal scheme for optimal search and stop",
abstract = "The problem of universal search and stop using an adaptive search policy is considered. When the target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal sequential 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 a missing target. 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.",
keywords = "Computational modeling, Error probability, Joints, Reliability, Search problems, Testing, Yttrium",
author = "Sirin Nitinawarat and Veeravalli, {Venugopal Varadachari}",
year = "2015",
month = "10",
day = "27",
doi = "10.1109/ITA.2015.7309008",
language = "English (US)",
series = "2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "322--328",
booktitle = "2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings",
address = "United States",

}

TY - GEN

T1 - Universal scheme for optimal search and stop

AU - Nitinawarat, Sirin

AU - Veeravalli, Venugopal Varadachari

PY - 2015/10/27

Y1 - 2015/10/27

N2 - The problem of universal search and stop using an adaptive search policy is considered. When the target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal sequential 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 a missing target. 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.

AB - The problem of universal search and stop using an adaptive search policy is considered. When the target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal sequential 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 a missing target. 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.

KW - Computational modeling

KW - Error probability

KW - Joints

KW - Reliability

KW - Search problems

KW - Testing

KW - Yttrium

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

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

U2 - 10.1109/ITA.2015.7309008

DO - 10.1109/ITA.2015.7309008

M3 - Conference contribution

AN - SCOPUS:84961794347

T3 - 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings

SP - 322

EP - 328

BT - 2015 Information Theory and Applications Workshop, ITA 2015 - Conference Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -