Testing with Non-identically Distributed Samples

We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we consider the following distributional property testing framework: Suppose there is a set of distributions over a discrete support of size k, p1, p2,ldots,pT, and we obtain c independent draws from each distribution. Suppose the goal is to learn or test a property of the average distribution, pavg. This setup models a number of important practical settings where the individual distributions correspond to heterogeneous entities -- either individuals, chronologically distinct time periods, spatially separated data sources, etc. From a learning standpoint, even with c=1 samples from each distribution, Theta(k/varepsilon2) samples are necessary and sufficient to learn pavg to within error varepsilon in ℓ1 distance. To test uniformity or identity -- distinguishing the case that pavg is equal to some reference distribution, versus has ℓ1 distance at least varepsilon from the reference distribution, we show that a linear number of samples in k is necessary given c=1 samples from each distribution. In contrast, for c ≥ 2, we recover the usual sublinear sample testing guarantees of the i.i.d. setting: we show that O(√k/varepsilon2 + 1/varepsilon4) total samples are sufficient, matching the optimal sample complexity in the i.i.d. case in the regime where varepsilon ≥ k-1/4. Additionally, we show that in the c=2 case, there is a constant ρ > 0 such that even in the linear regime with ρ k samples, no tester that considers the multiset of samples (ignoring which samples were drawn from the same pi) can perform uniformity testing. We also extend our techniques to the problem of testing "closeness" of two distributions.