Testing Poisson Binomial Distributions

A Poisson Binomial distribution over n variables is the distribution of the sum of n independent Bernoullis. We provide a sample near-optimal algorithm for testing whether a distribution P supported on {0, …, n } to which we have sample access is a Poisson Binomial distribution, or far from all Poisson Binomial distributions. The sample complexity of our algorithm is O ( n 1/4 ) to which we provide a matching lower bound. We note that our sample complexity improves quadratically upon that of the naive “learn followed by tolerant-test” approach, while instance optimal identity testing [VV14] is not applicable since we are looking to simultaneously test against a whole family of distributions.

Authors

• Jayadev Acharya
• Constantinos Daskalakis

Keywords

No keywords are indexed for this paper.