Testing Properties of Multiple Distributions with Few Samples

11/17/2019
by   Maryam Aliakbarpour, et al.
0

We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from s distributions, p_1, p_2, ..., p_s, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the p_i's are uniform or ϵ-far from being uniform in ℓ_1-distance (2) Identity Testing: Testing whether all the p_i's are equal to an explicitly given distribution q or ϵ-far from q in ℓ_1-distance, and (3) Closeness Testing: Testing whether all the p_i's are equal to a distribution q which we have sample access to, or ϵ-far from q in ℓ_1-distance. By assuming an additional natural condition about the source distributions, we provide sample optimal testers for all of these problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset