$\ell_p$ Testing and Learning of Discrete Distributions

The classic problems of testing uniformity of and learning a discrete distribution, given access to independent samples from it, are examined under general lp metrics. The intuitions and results often contrast with the classic l1 case. For p > 1, we can learn and test with a number of samples that is independent of the support size of the distribution: For 1 < p < 2, with a lp distance parameter ε, O(ü√1/εq) samples suffice for testing uniformity and O(1/εq) samples suffice for learning, where q=p/(p-1) is the conjugate of p. These bounds are tight precisely when the support size n of the distribution exceeds 1/εq, which seems to act as an upper bound on the "apparent" support size.