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.

Request changes or add full text files to a record

Actions (login required)

View Item