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₁ independent draws from an unknown distribution p with discrete support, and m₂ 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‖₁ ≥ ε. If p and q are supported on at most n elements, then our test is successful with high probability provided m₁ ≥ n^2/3/ε^4/3 and m₂ = Ω (max{n/√m₁ ε², √n/ε²}). We show that this tradeoff is information theoretically optimal throughout this range in the dependencies on all parameters, n, m₁, 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.