Testing Closeness With Unequal Sized Samples
We consider the problem of testing whether two unequal-sized samples were drawn from identical distributions, versus distributions that differ significantly. Specifically, given a target error parameter ε > 0, m 1 independent draws from an unknown distribution p with discrete support, and m 2 draws from an unknown distribution q of discrete support, we describe a test for distinguishing the case that p = q from the case that ||p − q|| 1 ≥ ε. If p and q are supported on at most n elements, then our test is successful with high probability provided m 1 ≥ n 2/3 /ε 4/3 and m 2 = Ω max{
We show that this tradeoff is information theoretically optimal throughout this range in the dependencies on all parameters, n, m 1 , and ε, to constant factors for worst-case distributions. As a consequence, we obtain an algorithm for estimating the mixing time of a Markov chain on n states up to a log n factor that usesÕ(n 3/2 τ mix ) queries to a "next node" oracle. The core of our testing algorithm is a relatively simple statistic that seems to perform well in practice, both on synthetic and on natural language data. We believe that this statistic might prove to be a useful primitive within larger machine learning and natural language processing systems.
The paper considers the problem of testing if two samples are from identical or very different distributions. This is an interesting question since in many practical scenarios, one of the data sources might be more precious/hard to obtain than the other. This paper characterizes the precise tradeoff between the sample lengths required to solve this problem, and also nail down the dependence on the accuracy, epsilon up to constant factors. From my understanding, the actual upper bounds (Achievability) bounds of [3] are actually nearly optimal (up to logarithmic terms), and this paper removes all spurious log-factors and reduces the exponent of epsilon to the optimal value. Even if the upper bound is a small improvement in terms of the number of samples, it still requires new insights and better testers, something the authors have managed to achieve. The lower bounds of the paper are similar to those in [8], [28] and matches the upper bounds shown up to constant factors.  Here are some specific comments on the paper:In Theorem 1, the authors require eps \ge n^{-1/12}. Is this because there is an additional term with higher powers ofepsilon, which disappears when this happens. If yes, it would be nice if the main result contains the entire complexity, and put the conditional result as a corollary. 98: uniform distribution minimizes the number of domain elements appearing more than once. This is slightly incorrect. Please rephrase as it maximizes the number of elements appearing once.108-112: I got a little confused with using n for domain size and then for # of samples when describing [1,2]. 217: should m1 be something else. I am not sure if it is n^{1-\gamma}. 270-278: the authors can give some further intuition and requirement of the additional step needed.321: Pois (O(1/\sqrt n)) ... should it be Pois(O(\sqrt n)).I am not fully sure what conclusions to draw from the experiments. I might be missing something elementary here. The paper is well written, and is an enjoyable read.