ECCC-Report TR20-062https://eccc.weizmann.ac.il/report/2020/062Comments and Revisions published for TR20-062en-usWed, 29 Apr 2020 06:23:33 +0300
Paper TR20-062
| Testing Data Binnings |
Clement Canonne,
Karl Wimmer
https://eccc.weizmann.ac.il/report/2020/062Motivated 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) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both over $[n]=\{1,2,\dots,n\}$, whether $\mathbf{p}$ equals $\mathbf{q}$, or is significantly different from it.
In this paper, we introduce the related question of identity up to binning, where the reference distribution $\mathbf{q}$ is over $k \ll n$ elements: the question is then whether there exists a suitable binning of the domain $[n]$ into $k$ intervals such that, once "binned," $\mathbf{p}$ is equal to $\mathbf{q}$. 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 (2019). Finally, we discuss several extensions and related research directions.Wed, 29 Apr 2020 06:23:33 +0300https://eccc.weizmann.ac.il/report/2020/062