ECCC-Report TR15-160https://eccc.weizmann.ac.il/report/2015/160Comments and Revisions published for TR15-160en-usFri, 29 Jan 2016 16:47:26 +0200
Revision 1
| Are Few Bins Enough: Testing Histogram Distributions |
Clement Canonne
https://eccc.weizmann.ac.il/report/2015/160#revision1A probability distribution over an ordered universe $[n]=\{1,\dots,n\}$ is said to be a $k$-histogram if it can be represented as a piecewise-constant function over at most $k$ contiguous intervals. We study the following question: given samples from an arbitrary distribution $D$ over $[n]$, one must decide whether $D$ is a $k$-histogram, or is far in $\ell_1$ distance from any such succinct representation. We obtain a sample and time-efficient algorithm for this problem, complemented by a nearly-matching information-theoretic lower bound on the number of samples required for this task. Our results significantly improve on the previous state-of-the-art, due to Indyk, Levi, and Rubinfeld (2012) and Canonne, Diakonikolas, Gouleakis, and Rubinfeld (2015).Fri, 29 Jan 2016 16:47:26 +0200https://eccc.weizmann.ac.il/report/2015/160#revision1
Paper TR15-160
| Are Few Bins Enough: Testing Histogram Distributions |
Clement Canonne
https://eccc.weizmann.ac.il/report/2015/160A probability distribution over an ordered universe $[n]=\{1,\dots,n\}$ is said to be a $k$-histogram if it can be represented as a piecewise-constant function over at most $k$ contiguous intervals. We study the following question: given samples from an arbitrary distribution $D$ over $[n]$, one must decide whether $D$ is a $k$-histogram, or is far in $\ell_1$ distance from any such succinct representation. We obtain a sample and time-efficient algorithm for this problem, complemented by a nearly-matching information-theoretic lower bound on the number of samples required for this task. Our results significantly improve on the previous state-of-the-art, due to Indyk, Levi, and Rubinfeld (2012) and Canonne, Diakonikolas, Gouleakis, and Rubinfeld (2015).Wed, 30 Sep 2015 16:21:40 +0300https://eccc.weizmann.ac.il/report/2015/160