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.

Text SODA10_006_adamaszekm.pdf Restricted 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 > Computer Science
Journal or Publication Title:	SIAM
Official Date:	17 January 2010
Dates:	Date Event 17 January 2010 Published
Page Range:	pp. 56-65
Identification Number:	10.1007/978-3-642-16367-8_13
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
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:	http://www.siam.org/meetings/da10/
URI:	http://wrap.warwick.ac.uk/id/eprint/47420

Request changes or add full text files to a record

Actions (login required)

View Item