Testing Monotone Continuous Distributions on High-dimensional Real Cubes
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. Published in: SIAM pp. 56-65.Full text not available from this repository.
Official URL: http://www.siam.org/proceedings/soda/2010/SODA10_0...
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|
|Date:||17 January 2010|
|Page Range:||pp. 56-65|
|Status:||Not Peer Reviewed|
|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|
Actions (login required)