Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Testing monotone continuous distributions on high-dimensional real cubes

Tools
- Tools
+ Tools

Adamaszek, Michał, Czumaj, Artur and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: Workshop on Property Testing, Tsinghua University, Peoples Republic of China. Published in: Property Testing : Current Research and Surveys, Vol.6390 pp. 228-233. doi:10.1007/978-3-642-16367-8_13 ISSN 0302-9743.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

We study the task of testing properties of probability distributions and our focus is on understanding the role of continuous distributions in this setting. 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 epsilon-far from it (in the statistical distance, with the L(1)-distance measure).

It is not difficult to see that for many natural distributions on infinite or uncountable domains, no algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no algorithm that tests if a given probability distribution on [0,1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions 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/epsilon(2)). This result is optimal up to a polylogarithmic factor. We also extend the result of Rubinfeld and Servedio (STOC'2005) to test if a distribution D on {0, 1,...,k}(n) is monotone with the sample complexity O(n/epsilon(2)).

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Distribution (Probability theory)
Journal or Publication Title: Property Testing : Current Research and Surveys
Publisher: Springer Verlag
ISSN: 0302-9743
Official Date: January 2010
Dates:
DateEvent
January 2010Published
Volume: Vol.6390
Page Range: pp. 228-233
DOI: 10.1007/978-3-642-16367-8_13
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Version or Related Resource: Adamaszek, M., et al. (2010). Testing monotone continuous distributions on high-dimensional real cubes. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms. Philadelphia: Society for Industrial and Applied Mathematics, pp. 56-65.
Conference Paper Type: Paper
Title of Event: Workshop on Property Testing
Type of Event: Workshop
Location of Event: Tsinghua University, Peoples Republic of China
Related URLs:
  • Related item in WRAP

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us