A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required to decide (w.h.p) if $D\in P$ or $d(D,P)>\epsilon$ ($d$ here is usually the $\ell_1$ distance). The most common measure of complexity is the number of samples used by the algorithm.
Now, in standard property testing, where you have query access to some object, a linear lower bound on query complexity is obviously the strongest lower bound possible, since $n$ queries would reveal the entire object. Is this the case for distribution testing as well?
As far as I understand, the "trivial" upper bound for testing properties of distributions is $O(n^2\log n)$ --- by Chernoff bounds, this is enough to "write down" a distribution D' which is close to D in $\ell_1$ distance, and then we can just check if there are any distributions close to D' which are in P (this might take infinite time, but this is irrelevant to sample complexity).
- Is there a better "trivial" test for all distribution properties?
- Are there any distribution properties for which we know sample lower bounds stronger than linear?