The Library
Testing monotone continuous distributions on high-dimensional real cubes
Tools
Tools
Tools
Adamaszek, Michał, Czumaj, Artur and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms. Philadelphia: SIAM, pp. 56-65. ISBN 9780898717013
Full text not available from this repository.Abstract
We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite (perhaps even uncountable) support Our goal is to test whether D has a given property of it is e-far nom it (in the statistical distance, with the L-1-distance measure) It is not difficult to see that for many natural distributions on infinite of uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there ale any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case of continuous [0, 1](n) cubes. We show that if a distribution D on [0,1](n) is monotone, then one can test if D is uniform with the sample complexity O(n/epsilon(2)) This result is optimal up to a polylogarithmic factor
| Item Type: | Book Item |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Computer Science Faculty of Science > Mathematics |
| Library of Congress Subject Headings (LCSH): | Distribution (Probability theory) |
| Journal or Publication Title: | PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS |
| Publisher: | SIAM |
| Place of Publication: | Philadelphia |
| ISBN: | 9780898717013 |
| Book Title: | Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms |
| Date: | 2010 |
| Number of Pages: | 10 |
| Page Range: | pp. 56-65 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Version or Related Resource: | Adamaszek, M., et al. (2010). Testing monotone continuous distributions on high-dimensional real cubes. Property Testing : Current Research and Surveys, 6390, pp. 228-233. |
| Title of Event: | 21st Annual ACM/SIAM Symposium on Discrete Algorithms |
| Location of Event: | Austin, TX |
| Date(s) of Event: | JAN 17-19, 2010 |
| Related URLs: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/5425 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
