Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-14
Computer Science
Data Structures and Algorithms
17 pages
Scientific paper
We consider the problem of distinguishing between two arbitrary black-box distributions defined over the domain [n], given access to $s$ samples from both. It is known that in the worst case O(n^{2/3}) samples is both necessary and sufficient, provided that the distributions have L1 difference of at least {\epsilon}. However, it is also known that in many cases fewer samples suffice. We identify a new parameter, that provides an upper bound on how many samples needed, and present an efficient algorithm that requires the number of samples independent of the domain size. Also for a large subclass of distributions we provide a lower bound, that matches our upper bound up to a poly-logarithmic factor.
Dar Eyal Even
Sandler Mark
No associations
LandOfFree
Telling Two Distributions Apart: a Tight Characterization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Telling Two Distributions Apart: a Tight Characterization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Telling Two Distributions Apart: a Tight Characterization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-521916