Optimality of coincidence-based goodness of fit test for sparse sample problems

We consider the sparse sample goodness of fit problem, where the number of samples n is smaller than the size of the alphabet m. The generalized error exponent based on large deviation analysis was proposed to characterize the performance of tests, using the high-dimensional model in which both n and m tend to infinity and n = o(m). In previous work, the best achievable probability of error is shown to decay -log(P_e) = (n²/m)(1 + o(1))J with upper and lower bounds on J. However, there is a significant gap between the two bounds. In this paper, we close the gap by proving a tight upper-bound, which matches the lower-bound over the entire region of generalized error exponents of false alarm and missed detection, achieved by the coincidence-based test. This implies that the coincidence-based test is asymptotically optimal.