2014/10/08 by Diakonikolas, Ilias, Kane, Daniel M., Nikishkin, Vladimir · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1410.2266
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 ε-far from p, in L1 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.