Testing identity of structured distributions

DOI10.1137/1.9781611973730.123MaRDI QIDQ5363068zbMATH OpenOpenAlexFDO

Authors Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

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.2266

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Combinatorics in computer science (68R05)

Abstract: We study the question of identity testing for structured distributions. More precisely, given samples from a {em structured} distribution $q$ over $[n]$ and an explicit distribution $p$ over $[n]$, we wish to distinguish whether $q=p$ versus $q$ is at least $epsilon$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.

Recommendations

• Testing shape restrictions of discrete distributions
• Testing shape restrictions of discrete distributions
• Sample-optimal identity testing with high probability
• Testing k-modal distributions: optimal algorithms via reductions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions

Cited in

(12)

• Hypothesis testing for high-dimensional multinomials: a selective review
• Testing shape restrictions of discrete distributions
• An automatic inequality prover and instance optimal identity testing
• Testing shape restrictions of discrete distributions
• Testing Ising models
• Sample-optimal identity testing with high probability
• Testing Boolean functions properties
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• On the Optimal Analysis of the Collision Probability Tester (an Exposition)
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Testing Data Binnings
• Attainability of two-point testing rates for finite-sample location estimation

This page was built for publication: Testing identity of structured distributions

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