2013 · 70 citations · 16 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityApproximation AlgorithmsComputational ComplexitySublinear AlgorithmsTime ComplexityComplexityDiscrete Probability DistributionsDistribution TestingLower BoundsLower Bounds For Randomized AlgorithmsSample ComplexitySample Complexity Analysis
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}).
16
Testing that distributions are close
Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld et al. · 2002 · 262 citations
Gregory Valiant, Paul Valiant · 2011 · 256 citations · Full text
Testing random variables for independence and identity
Tuğkan Batu, E. Fischer, Lance Fortnow et al. · 2001 · 195 citations
Testing Closeness of Discrete Distributions
Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld et al. · Journal of the ACM · 2013 · 145 citations