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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| 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 |