# Testing Closeness With Unequal Sized Samples

arXiv: https://arxiv.org/abs/1504.04599 · HTML: https://mlsanity.com/paper/1504.04599/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2015.

## Built on by (most cited first, 4 of 4)

- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach](https://mlsanity.com/paper/2507.12843/) (2025)
- [A Distribution Testing Approach to Clustering Distributions](https://mlsanity.com/paper/2512.08376/) (2025)

## Abstract (arXiv)

We consider the problem of closeness testing for two discrete distributions in the practically relevant setting of unequal sized samples drawn from each of them. Specifically, given a target error parameter varepsilon > 0, m1 independent draws from an unknown distribution p, and m2 draws from an unknown distribution q, we describe a test for distinguishing the case that p=q from the case that ||p-q||1 ≥ varepsilon. If p and q are supported on at most n elements, then our test is successful with high probability provided m1≥ n2/3/varepsilon4/3 and m2 = Omega(maxfracn√ m1varepsilon2, frac√ nvarepsilon2); we show that this tradeoff is optimal throughout this range, to constant factors. These results extend the recent work of Chan et al. who established the sample complexity when the two samples have equal sizes, and tightens the results of Acharya et al. by polynomials factors in both n and varepsilon. 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 tildeO(n3/2 τmix) queries to a "next node" oracle, improving upon the tildeO(n5/3τmix) query algorithm of Batu et al. Finally, we note that the core of our testing algorithm is a relatively simple statistic that seems to perform well in practice, both on synthetic data and on natural language data.