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

How many independent samplesNdo we need from a distributionpto decide thatpis epsiv-distant from uniform in an L1sense, Sigmai=1m|p(i) - 1/m| > epsiv? (Heremis the number of bins on which the distribution is supported, and is assumed knownapriori.) Somewhat surprisingly, we only needNepsiv2Gtm1/2to 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.