Quickest Search Over Multiple Sequences
Quickest Search Over Multiple Sequences
复制标题
多个序列的最快搜索
DOI：
--
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Georgios Georgiadis
中科院分区：
文献类型：
--
作者：
L. Lai;H. Poor;Yan Xin;Georgios Georgiadis
考虑了从一个概率分布Q1中选取多个序列，通过对多个序列进行搜索，依次找到一个独立的同分布序列的问题，其中一些序列来自Q1，另一些序列来自不同的分布Q0。在所考虑的问题中，假设分布Q1的序列数是一个随机变量，其值未知。在贝叶斯公式中，导出了一个顺序决策规则，该规则优化了假警报概率和决策所需样本数量之间的权衡。在一次可以观察到一个序列的情况下，表明累积和（CUSUM）检验对于所研究的问题是最优的，它是众所周知的非贝叶斯统计变点检测公式的最优性。具体来说，CUSUM测试是在第一个序列上运行的。如果在CUSUM测试中发生重置事件，则放弃正在检查的序列，并将规则切换到下一个序列。如果CUSUM测试停止，那么规则声明测试停止时正在检查的序列是由Q1生成的。这个结果是通过假设存在无限多个序列而得出的，这样一个序列已经检测过一次就不会再测试了。如果有有限多个序列，结果在无内存条件下也是有效的。给出了最优顺序决策规则的性能表达式。考虑了多个序列可以同时检测的一般情况。导出了这种一般情况下的最优解。
The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distribution Q1 by searching over multiple sequences, some of which are drawn from Q1 and the others of which are drawn from a different distribution Q0, is considered. In the problem considered, the number of sequences with distribution Q1 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 Q1 . 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.