The Minimax Risk in Testing Uniformity Over Large Alphabets Under Missing-Ball Alternatives

We study the problem of testing the goodness of fit of occurrences of items from many categories to a Poisson distribution uniform over the categories, against a class of alternative hypotheses obtained by the removal of an ℓpball,p≤ 2, of radius ϵ around the sequence of uniform Poisson rates. We characterize the minimax risk for this problem as the expected number of samplesnand the number of categoriesNgo to infinity. Our result enables the comparison at the constant level of the many estimators previously proposed for this problem, rather than at the rate of convergence of the risk or the scaling order of the sample complexity. The minimax test relies exclusively on collisions in the small sample limit but behaves like the chisquared test otherwise. Empirical studies over a range of problem parameters show that the asymptotic risk estimate is accurate in finite samples and that the minimax test is significantly better than the chisquared test or a test that only uses collisions. Our analysis involves the reduciion to a structured subset of alternatives, establishing asymptotic normality for linear statistics, and solving an optimization problem overN-dimensional sequences that parallels classical results from Gaussian white noise models.