2026-08-11T07:38:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12627 2024-03-06T10:51:17Z ddc:004 open_access

Testing Data Binnings Canonne, Clément L. Wimmer, Karl property testing distribution testing identity testing hypothesis testing Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) 𝐪 and samples from an unknown distribution 𝐩, both over [n] = {1,2,… ,n}, whether 𝐩 equals 𝐪, or is significantly different from it. In this paper, we introduce the related question of identity up to binning, where the reference distribution 𝐪 is over k ≪ n elements: the question is then whether there exists a suitable binning of the domain [n] into k intervals such that, once "binned," 𝐩 is equal to 𝐪. We provide nearly tight upper and lower bounds on the sample complexity of this new question, showing both a quantitative and qualitative difference with the vanilla identity testing one, and answering an open question of Canonne [Clément L. Canonne, 2019]. Finally, we discuss several extensions and related research directions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Karl Wimmer 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.24 urn:nbn:de:0030-drops-126277 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode