Testing Closeness of Discrete Distributions

Testing Closeness of Discrete Distributions

Given samples from two distributions over an n-element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in n, specifically, O(n[superscript 2/3]ε[superscript −8/3] log n), independent samples from each distribution, runs in time l...

Full description

Bibliographic Details
Main Authors: Batu, Tugkan, Fortnow, Lance, Rubinfeld, Ronitt, Smith, Warren D., White, Patrick
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Association for Computing Machinery (ACM) 2014
Online Access:http://hdl.handle.net/1721.1/90630
https://orcid.org/0000-0002-4353-7639

Internet

http://hdl.handle.net/1721.1/90630
https://orcid.org/0000-0002-4353-7639

Similar Items