Testing properties of distributions
Ronitt Rubinfeld, Tuğkan Batu · 2001
We study the sample complexity of several basic statistical inference tasks as a function of the domain size for the underlying discrete probability distributions. Given access only to samples from two distributions over an n-element set, we want to distinguish identical pairs of distributions from pairs of distributions that have large statistical distance. We give an algorithm that uses O(n2/3 log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the case that the statistical distance between the distributions is small from the case that it is large. We also prove a lower bound of Ω(n2/3) for the sample complexity. Under a related model, we show how to test, given access to samples from a distribution over an n-element set, whether the distribution is statistically close to an explicitly specified distribution. Our test uses O(n1/2) samples, which matches the known tight bounds for the case when the explicit distribution is uniform. Given access to independent samples of a distribution A over the product space of two sets with n and m elements, respectively, we show how to test whether the distributions induced by A restricted to each component are independent, i.e., whether A is statistically close to A1 × A2 for some A1 over an n-element set and A2 over an m-element set. The sample complexity of our test is O(n 2/3m1/3), assuming without loss of generality that m ≤ n. We also give a matching lower bound up to polylogarithmic factors. We consider the problem of approximating the entropy of a black-box discrete distribution in sublinear time. We show that a g -multiplicative approximation to the entropy can be obtained in Odn 1+z/g2 time for distributions with sufficiently high entropy where n is the size of the domain of the distribution and z is an arbitrarily small positive constant. We show that one cannot get a multiplicative approximation to the entropy in general. Even for the class of distributions to which our upper bound applies, we show a lower bound of Wn1/2g2 .