Large Deviations for Statistical Sequence Matching

We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan (TIT 2015) and derive achievable theoretical performance guar-antees for a generalized likelihood ratio test (G LRT) in the large deviations regime, when the number of matched pairs of sequences between two databases is unknown. In this case, the task is to accurately estimate the number of matched pairs and identify the matched pairs of sequences among all possible matches between the sequences in the two databases. We generalize the GLRT by Unnikrishnan and explicitly characterize the tradeoff among the exponential decay rates for probabilities of mismatch, false reject and false alarm. When one of the two databases contains a single sequence, the problem of statistical sequence matching specializes to the problem of multiple classification introduced by Gutman (TIT 1989). For this special case, our result strengthens previous result of Gutman (TIT 1989) and Zhou, Tan and Motani (Information and Inference 2020) by allowing the testing sequence to be generated from a distribution that is different from generating distributions of all training sequences.