# Testing Poisson Binomial Distributions

arXiv: https://arxiv.org/abs/1410.3386 · HTML: https://mlsanity.com/paper/1410.3386/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2014.

## Built on by (most cited first, 1 of 1)

- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)

## Abstract (arXiv)

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(n1/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.