Optimal Algorithms for Testing Closeness of Discrete Distributions

Siu-On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant

2013 · 70 citations · 16 references

DOIFull text

Open access

Concepts

Abstract

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions p and q over an n-element set, we wish to distinguish whether p = q versus p is at least ∊-far from q, in either ℓ1 or ℓ2 distance. Batu et al [BFR+00, BFR+13] gave the first sub-linear time algorithms for these problems, which matched the lower bounds of [Val11] up to a logarithmic factor in n, and a polynomial factor of ∊. In this work, we present simple testers for both the ℓ1 and ℓ2 settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on n, and the dependence on ∊; for the ℓ1 testing problem we establish that the sample complexity is Θ(max{n2/3/∊4/3,n1/2/∊2}).

References

16