Sharp Bounds for Generalized Uniformity Testing

We study the problem of generalized uniformity testing citeBC17 of a discrete probability distribution: Given samples from a probability distribution p over an em unknown discrete domain Omega, we want to distinguish, with probability at least 2/3, between the case that p is uniform on some em subset of Omega versus ε-far, in total variation distance, from any such uniform distribution. We establish tight bounds on the sample complexity of generalized uniformity testing. In more detail, we present a computationally efficient tester whose sample complexity is optimal, up to constant factors, and a matching information-theoretic lower bound. Specifically, we show that the sample complexity of generalized uniformity testing is Thetaleft(1/(ε4/3|p|3) + 1/(ε2 |p|2) right).