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 to a record

Actions (login required)

View Item