2026-07-23T17:31:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7493 2024-03-12T11:58:26Z ddc:004 open_access

Near-Optimal Closeness Testing of Discrete Histogram Distributions Diakonikolas, Ilias Kane, Daniel M. Nikishkin, Vladimir distribution testing histograms closeness testing We investigate the problem of testing the equivalence between two discrete histograms. A k-histogram over [n] is a probability distribution that is piecewise constant over some set of k intervals over [n]. Histograms have been extensively studied in computer science and statistics. Given a set of samples from two k-histogram distributions p, q over [n], we want to distinguish (with high probability) between the cases that p = q and ||p ? q||_1 >= epsilon. The main contribution of this paper is a new algorithm for this testing problem and a nearly matching information-theoretic lower bound. Specifically, the sample complexity of our algorithm matches our lower bound up to a logarithmic factor, improving on previous work by polynomial factors in the relevant parameters. Our algorithmic approach applies in a more general setting and yields improved sample upper bounds for testing closeness of other structured distributions as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilias Diakonikolas and Daniel M. Kane and Vladimir Nikishkin 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.8 urn:nbn:de:0030-drops-74937 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode