Large and Small Deviations for Statistical Sequence Matching
作者：周琳 时间：2026年10月01日 12:10 点击数：
语言：English
发表刊物：IEEE Transactions on Information Theory
发表日期：2024年11月25日
摘要：
We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan, (2015) and derive theoretical performance guarantees for the generalized likelihood ratio test (GLRT). We first consider the case where the number of matched pairs of sequences between the databases is known. In this case, the task is to accurately find the matched pairs of sequences among all possible matches between the sequences in the two databases. We analyze the performance of the GLRT by Unnikrishnan and explicitly characterize the tradeoff between the mismatch and false reject probabilities under each hypothesis in both large and small deviations regimes. Furthermore, we demonstrate the optimality of Unnikrishnan’s GLRT test under the generalized Neyman-Person criterion for both regimes and illustrate our theoretical results via numerical examples. Subsequently, we generalize our achievability analyses to the case where the number of matched pairs is unknown, and an additional error probability needs to be considered. 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, (1989). For this special case, our result for the small deviations regime strengthens previous result of Zhou et al., (2020) by removing unnecessary conditions on the generating distributions.
原文链接
