2025/06/04 by Lin Zhou, Qianyun Wang, Zhou, Lin +5
Computer Science · Decision Sciences · #Advanced Statistical Process Monitoring #Data Quality and Management #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Signal Processing (eess.SP) #Statistics Theory (math.ST) #Time Series Analysis and Forecasting #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2506.03976
openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the problem of statistical sequence matching initiated by Unnikrishnan (TIT 2015) and derive theoretical performance guarantees for sequential tests that have bounded expected stopping times. Specifically, in this problem, one is given two databases of sequences and the task is to identify all matched pairs of sequences. In each database, each sequence is generated i.i.d. from a distinct distribution and a pair of sequences is said matched if they are generated from the same distribution. The generating distribution of each sequence is unknown. We first consider the case where the number of matches is known and derive the exact exponential decay rate of the mismatch (error) probability, a.k.a. the mismatch exponent, under each hypothesis for optimal sequential tests. Our results reveal the benefit of sequentiality by showing that optimal sequential tests have larger mismatch exponent than fixed-length tests by Zhou et al. (TIT 2024). Subsequently, we generalize our achievability result to the case of unknown number of matches. In this case, two additional error probabilities arise: false alarm and false reject probabilities. We propose a corresponding sequential test, show that the test has bounded expected stopping time under certain conditions, and characterize the tradeoff among the exponential decay rates of three error probabilities. Furthermore, we reveal the benefit of sequentiality over the two-step fixed-length test by Zhou et al. (TIT 2024) and propose an one-step fixed-length test that has no worse performance than the fixed-length test by Zhou et al. (TIT 2024). When specialized to the case where either database contains a single sequence, our results specialize to large deviations of sequential tests for statistical classification, the binary case of which was recently studied by Hsu, Li and Wang (ITW 2022).