Quickest Linear Search over Correlated Sequences

Consider a set of random sequences, each consisting of independent and identically distributed random variables drawn from one of the two known distributions <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$F_{0}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$F_{1}$ </tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$F_{1}$ </tex-math></inline-formula> . 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.