Quickest search for a rare distribution

We consider the problem of finding one sequence of independent random variables following a rare atypical distribution, P₁, amongst a large number of sequences following some null distribution, P₀. We quantify the number of samples needed to correctly identify one atypical sequence as the atypical sequences become increasingly rare. We show that the known optimal procedure, which consists of a series of sequential probability ratio tests, succeeds with high probability provided the number of samples grows at a rate equal to a constant times π^-1 D(P₁∥P₀)^-1, where π is the prior probability of a sequence being atypical, and D(P₁∥P₀) is the Kullback-Leibler divergence. Using techniques from sequential analysis, we show that if the number of samples grow at a rate equal to π^-1 D(P₁∥P₀)^-1, any procedure fails. This is then compared to sequential thresholding [1], a simple procedure which can be implemented without exact knowledge of distribution P₁. We also show that the SPRT and sequential thresholding are fairly robust to our knowledge of π. Lastly, a lower bound for non-sequential procedures is derived for comparison.