Sparse Uniformity Testing
Bhaswar B. Bhattacharya, Rajarshi Mukherjee · IEEE Transactions on Information Theory · 2024
In this paper we consider the uniformity testing problem for high-dimensional discrete distributions (multinomials) under sparse alternatives. Specifically, we derive sharp detection thresholds for testing, based on n samples, whether a discrete distribution supported on d elements differs from the uniform distribution in at most s (out of the d) coordinates and is$\varepsilon $-far (in total variation distance) from uniformity. Our results reveal various interesting phase transitions which depend on the interplay of the sample size n and the signal strength$\varepsilon $with the dimension d and the sparsity level s. For instance, if the sample size is less than a threshold (which depends on d and s), then all tests are asymptotically powerless, irrespective of the magnitude of the signal strength. On the other hand, if the sample size is above the threshold, then the detection boundary undergoes a further phase transition depending on the signal strength. Here, a$\chi ^{2}$-type test attains the detection boundary in the dense regime, whereas in the sparse regime a Bonferroni correction of two maximum-type tests and a version of the Higher Criticism test is optimal up to sharp constants. These results combined provide a complete description of the phase diagram for the sparse uniformity testing problem across all regimes of the parameters n, d, s, and$\varepsilon $. One of the challenges in dealing with multinomials is that the parameters are always constrained to lie in the simplex. This results in a layered phase transition phenomenon in the parameter space. Specifically, there is a critical sample complexity (depending only on d) below which all tests are asymptotically powerless irrespective of the signal strength and above which there is a critical threshold for the signal strength that determines testability.