A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data

How many independent samples N do we need from a distribution p to decide that p is epsiv-distant from uniform in an L₁ sense, Sigma_i=1 ^m |p(i) - 1/m| > epsiv? (Here m is the number of bins on which the distribution is supported, and is assumed known a priori.) Somewhat surprisingly, we only need N epsiv² Gt m ^1/2 to make this decision reliably (this condition is both sufficient and necessary). The test for uniformity introduced here is based on the number of observed ldquocoincidencesrdquo (samples that fall into the same bin), the mean and variance of which may be computed explicitly for the uniform distribution and bounded nonparametrically for any distribution that is known to be epsiv-distant from uniform. Some connections to the classical birthday problem are noted.