# Sharp Bounds for Generalized Uniformity Testing

arXiv: https://arxiv.org/abs/1709.02087 · HTML: https://mlsanity.com/paper/1709.02087/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2017.

## Built on by (most cited first, 3 of 3)

- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)

## Abstract (arXiv)

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).