Quickest sequential search over correlated sequences

摘要

Quickest sequential search aims to find a sequence with a desired statistical feature from a pool of given sequences. The existing literature addresses the quickest search problem of interest when the sequences are generated independently. This paper focuses on a setting in which the generation of sequences follows a dependency kernel, where the likelihood that a sequence is generated by the desired distribution depends on the distribution of is preceding sequence. This paper characterizes the quickest sequential search procedure, that is the procedure that optimizes a balance between the quality of decision and the agility of the search process, as two opposing performance measures. The analysis reveals that the optimal decision rules have computationally efficient closed-form structure. Numerical evaluations confirm the gains of this optimal solution over the existing approaches.