# ℓp Testing and Learning of Discrete Distributions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2014.

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

- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Identity testing of reversible Markov chains](https://mlsanity.com/paper/2105.06347/) (2021)
- [Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates](https://mlsanity.com/paper/2211.08580/) (2022)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains](https://mlsanity.com/paper/2302.08059/) (2023)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)

## Abstract (arXiv)

The classic problems of testing uniformity of and learning a discrete distribution, given access to independent samples from it, are examined under general ℓp metrics. The intuitions and results often contrast with the classic ℓ1 case. For p > 1, we can learn and test with a number of samples that is independent of the support size of the distribution: With an ℓp tolerance ε, O(max √1/εq, 1/ε2 ) samples suffice for testing uniformity and O(max 1/εq, 1/ε2) samples suffice for learning, where q=p/(p-1) is the conjugate of p. As this parallels the intuition that O(√n) and O(n) samples suffice for the ℓ1 case, it seems that 1/εq acts as an upper bound on the "apparent" support size. For some ℓp metrics, uniformity testing becomes easier over larger supports: a 6-sided die requires fewer trials to test for fairness than a 2-sided coin, and a card-shuffler requires fewer trials than the die. In fact, this inverse dependence on support size holds if and only if p > frac43. The uniformity testing algorithm simply thresholds the number of "collisions" or "coincidences" and has an optimal sample complexity up to constant factors for all 1 ≤ p ≤ 2. Another algorithm gives order-optimal sample complexity for ℓ∞ uniformity testing. Meanwhile, the most natural learning algorithm is shown to have order-optimal sample complexity for all ℓp metrics. The author thanks Cl'ement Canonne for discussions and contributions to this work.