
The Library
Testing monotone continuous distributions on high-dimensional real cubes
Tools
Czumaj, Artur, Adamaszek, Michał and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010. Published in: SIAM pp. 56-65. doi:10.1007/978-3-642-16367-8_13
![]() |
Text
SODA10_006_adamaszekm.pdf Embargoed item. Restricted access to Repository staff only Download (699Kb) |
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 or it is "-far from it (in the statistical distance,
with the L1-distance measure).
It is not difficult to see that for many natural dis-
tributions on infinite or uncountable domains, no test-
ing algorithm can exist and the central objective of our
study is to understand if there are any nontrivial dis-
tributions 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 uni-
form. We show however, that if some additional infor-
mation about the input distribution is known, testing
uniform distribution is possible. We extend the recent
result about testing uniformity for monotone distribu-
tions 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="2). This result is optimal up
to a polylogarithmic factor.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | SIAM | ||||
Official Date: | 17 January 2010 | ||||
Dates: |
|
||||
Page Range: | pp. 56-65 | ||||
DOI: | 10.1007/978-3-642-16367-8_13 | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10) | ||||
Type of Event: | Conference | ||||
Location of Event: | Austin, Texas | ||||
Date(s) of Event: | 17-19 Jan 2010 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |