Quickest Linear Search over Correlated Sequences

Javad Heydari, Ali Tajer, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


Consider a set of random sequences, each consisting of independent and identically distributed random variables drawn from one of the two known distributions F0 and F1. The underlying distributions of different sequences are correlated, induced by an inherent physical coupling in the mechanisms generating these sequences. The objective is to design the quickest data-adaptive and sequential search procedure for identifying one sequence generated according to F1. The optimal design involves striking a balance between the average delay in reaching a decision and the rate of false alarms, as two opposing figures of merit. Optimal and asymptotically optimal decision rules are derived, which can take radically different forms depending on the correlation structure. Performance and sampling complexity analyses are provided to delineate the tradeoff between decision delay and quality. The generalization to parallel sampling, in which multiple sequences are sampled at the same time, is also investigated.

Original languageEnglish (US)
Article number7518609
Pages (from-to)5786-5808
Number of pages23
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Anomaly detection
  • Sequential sampling
  • correlated sequences
  • quickest search


Dive into the research topics of 'Quickest Linear Search over Correlated Sequences'. Together they form a unique fingerprint.

Cite this