Testing Poisson binomial distributions

DOI10.1137/1.9781611973730.122MaRDI QIDQ5363067zbMATH OpenOpenAlexFDO

Authors Jayadev Acharya, Constantinos Daskalakis

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3386

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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,\mathrm{...},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.

Recommendations

• Binomial approximation to the Poisson binomial distribution
• Testing shape restrictions of discrete distributions
• Testing shape restrictions of discrete distributions

Cited in

(8)

• Testing shape restrictions of discrete distributions
• Mean distance test of Poisson distribution
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• scientific article; zbMATH DE number 1089160 (Why is no real title available?)
• Testing for the bivariate Poisson distribution
• Preference-based online learning with dueling bandits: a survey
• Optimal stopping rules for sequential hypothesis testing
• scientific article; zbMATH DE number 7307484 (Why is no real title available?)

This page was built for publication: Testing Poisson binomial distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363067)