Conference proceeding
Quickest search over multiple sequences with mixed observations
2013 IEEE International Symposium on Information Theory, pp.2582-2586
07/2013
DOI: 10.1109/ISIT.2013.6620693
Abstract
The problem of sequentially finding an independent and identically distributed (i.i.d.) sequence that is drawn from a probability distribution F 1 by searching over multiple sequences, some of which are drawn from F 1 and the others of which are drawn from a different distribution F 0 , is considered. The sensor is allowed to take one observation at a time. It has been shown in a recent work that if each observation comes from one sequence, Cumulative Sum (CUSUM) test is optimal. In this paper, we propose a new approach in which each observation can be a linear combination of samples from multiple sequences. The test has two stages. In the first stage, namely scanning stage, one takes a linear combination of a pair of sequences with the hope of scanning through sequences that are unlikely to be generated from F 1 and quickly identifying a pair of sequences such that at least one of them is highly likely to be generated by F 1 . In the second stage, namely refinement stage, one examines the pair identified from the first stage more closely and picks one sequence to be the final sequence. The problem under this setup belongs to a class of multiple stopping time problems. In particular, it is an ordered two concatenated Markov stopping time problem. We obtain the optimal solution using the tools from the multiple stopping time theory. Numerical simulation results show that this search strategy can significantly reduce the searching time, especially when F 1 is rare.
Details
- Title: Subtitle
- Quickest search over multiple sequences with mixed observations
- Creators
- Jun Geng - Dept. of Electr. & Comput. Eng., Worcester Polytech. Inst., Worcester, MA, USAWeiyu Xu - University of IowaLifeng Lai - Dept. of Electr. & Comput. Eng., Worcester Polytech. Inst., Worcester, MA, USA
- Resource Type
- Conference proceeding
- Publication Details
- 2013 IEEE International Symposium on Information Theory, pp.2582-2586
- Publisher
- IEEE
- DOI
- 10.1109/ISIT.2013.6620693
- ISSN
- 2157-8095
- eISSN
- 2157-8117
- Language
- English
- Date published
- 07/2013
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197313502771
Metrics
9 Record Views