Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-021 | 18th February 2014 05:43

#### Testing probability distributions underlying aggregated data

TR14-021
Authors: Clement Canonne, Ronitt Rubinfeld
Publication: 18th February 2014 19:28
In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended dual access models, in which the algorithm $A$ can both sample from $D$ and respectively, for any $i\in[n]$,
- query the probability mass $D(i)$ (query access); or
- get the total mass of $\{1,\dots,i\}$, i.e. $\sum_{j=1}^i D(j)$ (cumulative access)